📂Graph Theory

Havel-Hakimi Algorithm Proof

Theorem

Let’s assume we are given a non-increasing sequence $D = (d_{1} , \cdots , d_{n})$. If $D$ is graphic, we can find a realization $G$ of $D$ using the following method:

• Step 1.
  Create a null graph with $n$ vertices $v_{1} , \cdots , v_{n}$.
• Step 2. $k = 1, \cdots , n$
  • Step 2-1.
    Connect $v_{k}$ to $v_{k+1} , \cdots , v_{d_{k} + 1}$.
  • Step 2-2.
    Decrease $d_{k+1} , \cdots , d_{d_{k}+1}$ by $1$.
  • Step 2-3.
    Substitute as $d_{k} \gets 0$. Repeat Step 2. until it becomes $D = (0,\cdots , 0)$.

If $D$ is graphic, there exists a realization $G$ where a vertex $v_{1}$ with degree $d_{1}$ is adjacent to $v_{2} , \cdots , v_{d_{1} + 1}$.

Description

The Havel-Hakimi algorithm is an algorithm that concretely finds a realization guaranteed by the existence of the Erdős-Gallai theorem. Its principle is simply to handle the vertex with the highest degree first to ensure no small remainders. By providing degrees first, it can directly be used to construct graphs with degree distributions in random graphs.

For example, with a sequence such as $(5,5,5,3,2,2,1,1)$, the realization obtained through the Havel-Hakimi algorithm would look like the one above. If time allows, it is recommended to try creating graphic sequences using the Erdős-Gallai theorem and find realizations manually without the Havel-Hakimi algorithm to see its usefulness.

Proof

Every time $D$ is updated, the maximum degree gradually decreases. It suffices for the node $v_{k}$ with the maximum degree to be adjacent to $v_{k+1} , \cdots , v_{d_{k} + 1}$ at each step, and showing that the first vertex $v_{1}$ with degree $d_{1}$ is adjacent to $v_{2} , \cdots , v_{d_{1} + 1}$ completes the proof by mathematical induction.

Assuming that the vertices of any realization $R$ of $D$ satisfy $\deg (v_{i}) = d_{i}$, let’s define the following two sets. $$T_{R} := \left\{ v_{2} , \cdots , v_{d_{1} + 1} \right\} \\ N_{R}(v_{1}) := \left\{ v \in V(R) : vv_{1} \in E(R) \right\}$$ In the definition, $T_{R}$ is the set collecting vertices after $v_{1}$ and within the next $d_{1}$, and $N_{R}(v_{1})$ is the neighborhood of $v_{1}$, i.e., the set of vertices actually adjacent to $v_{1}$ in $R$. Let’s consider the following integer $t_{R}$. $$t_{R} := \left| N_{R} (v_{1}) \cap T_{R} \right|$$ Now, it must be shown that $G$ is the realization of $D$ that maximizes $t_{G}$. In other words, it satisfies $T_{G} = N_{G}(v_{1})$ and $t_{G} = d_{1}$, meaning that the vertex $v_{1}$ with degree $d_{1}$ is adjacent to $v_{2} , \cdots , v_{d_{1} + 1}$. If $t_{G} = d_{1}$, $T_{G} = N_{G}(v_{1})$ naturally follows, making $G$ the realization that maximizes $t_{G}$ without further proof. Now, assuming the case of $t_{G} < d_{1}$, if another realization $G'$ of $D$ exists that makes $t_{G'} = t_{G} + 1$

In the case of $t_{G'}<d_{1}$, $v_{1}$ must be adjacent to some $v_{y} \in T_{G'}^{c}$ instead of any $v_{x} \in T_{G'}$. The red dotted line in the above figure represents the edge that exists in $G$ but is removed in $G'$, and the red solid line is the newly created edge because the degree of $v_{1}$ must remain constant.

Just as with $v_{1}$, the degrees of $v_{x}$ and $v_{y}$ must be maintained, so one must choose one $v_{z}$, which originally was not adjacent to $v_{x}$ but was to $v_{y}$ in $G$, add $v_{x} v_{z}$, and remove $v_{y} v_{z}$. This way, the original degree sequence $D$ does not change at all, and $G'$ can be considered a realization of $D$. However, since $G'$ misses one $v_{x}$ from $T_{G'}$ and adds one $v_{y}$ to $N_{G'}(v_{1})$, $t_{G'}$ actually becomes smaller than $t_{G}$. This contradicts the existence of the realization $G'$ that satisfies $t_{G'} = t_{G} + 1$, thereby necessitating $t_{G} = d_{1}$. In other words, the vertex $v_{1}$ in realization $G$ is adjacent to $v_{2} , \cdots , v_{d_{1} + 1}$.

■