Havel–Hakimi algorithm

The Havel-Hakimi algorithm is based on the following theorem.

Let $A\; =\; (s,\; t\_\{1\},...,\; t\_\{s\},\; d\_\{1\},...,\; d\_\{n\})$ be a finite list of nonnegative integers that is nonincreasing. Let $A\text{'}\; =\; (t\_\{1\}-1,...,\; t\_\{s\}-1,\; d\_\{1\},...,\; d\_\{n\})$ be a second finite list of nonnegative integers that is rearranged to be nonincreasing. List $A$ is graphic if and only if list $A\text{'}$ is graphic.

If the given list $A$ is graphic, then the theorem will be applied at most $n-1$ times setting in each further step $A:=A\text{'}$. Note that it can be necessary to sort this list again. This process ends when the whole list $A\text{'}$ consists of zeros. Let $G$ be a simple graph with the degree sequence $A$: Let the vertex $S$ have degree $s$; let the vertices $T\_\{1\},...,\; T\_\{s\}$ have respective degrees $t\_\{1\},...,\; t\_\{s\}$; let the vertices $D\_\{1\},...,\; D\_\{n\}$ have respective degrees $d\_\{1\},...,\; d\_\{n\}$. In each step of the algorithm, one constructs the edges of a graph with vertices $T\_\{1\},...,\; T\_\{s\}$—i.e., if it is possible to reduce the list $A$ to $A\text{'}$, then we add edges $\backslash \{S,T\_1\backslash \},\backslash \{S,T\_2\backslash \},\backslash cdots,\backslash \{S,T\_\{s\}\backslash \}$. When the list $A$ cannot be reduced to a list $A\text{'}$ of nonnegative integers in any step of this approach, the theorem proves that the list $A$ from the beginning is not graphic.

The following is a summary based on the proof of the Havel-Hakimi algorithm in Invitation to Combinatorics (Shahriari 2022).

To prove the Havel-Hakimi algorithm always works, assume that $A\text{'}$ is graphic, and there exists a simple graph $G\text{'}$ with the degree sequence $A\text{'}\; =\; (t\_\{1\}-1,...,\; t\_\{s\}-1,\; d\_\{1\},...,\; d\_\{n\})$. Then we add a new vertex $v$ adjacent to the $s$ vertices with degrees $t\_\{1\}-1,...,\; t\_\{s\}-1$ to obtain the degree sequence $A$.

To prove the other direction, assume that $A$ is graphic, and there exists a simple graph $G$ with the degree sequence $A\; =\; (s,\; t\_\{1\},...,\; t\_\{s\},\; d\_\{1\},...,\; d\_\{n\})$ and vertices $S,\; T\_\{1\},...,\; T\_\{s\},\; D\_\{1\},...,\; D\_\{n\}$. We do not know which $s$ vertices are adjacent to $S$, so we have two possible cases.

In the first case, $S$ is adjacent to the vertices $T\_\{1\},...,\; T\_\{s\}$ in $G$. In this case, we remove $S$ with all its incident edges to obtain the degree sequence $A\text{'}$.

In the second case, $S$ is not adjacent to some vertex $T\_\{i\}$ for some $1\; \backslash leq\; i\; \backslash leq\; s$ in $G$. Then we can change the graph $G$ so that $S$ is adjacent to $T\_\{i\}$ while maintaining the same degree sequence $A$. Since $S$ has degree $s$, the vertex $S$ must be adjacent to some vertex $D\_\{j\}$ in $G$ for $1\; \backslash leq\; j\; \backslash leq\; n$: Let the degree of $D\_\{j\}$ be $d\_\{j\}$. We know $t\_i\; \backslash geq\; d\_j$, as the degree sequence $A$ is in non-increasing order.

Since $t\_i\; \backslash geq\; d\_j$, we have two possibilities: Either $t\_i\; =\; d\_j$, or $t\_i\; >\; d\_j$. If $t\_i\; =\; d\_j$, then by switching the places of the vertices $T\_\{i\}$ and $D\_\{j\}$, we can adjust $G$ so that $S$ is adjacent to $T\_\{i\}$ instead of $D\_\{j\}.$ If $t\_i\; >\; d\_j$, then since $T\_\{i\}$ is adjacent to more vertices than $D\_\{j\}$, let another vertex $W$ be adjacent to $T\_\{i\}$ and not $D\_\{j\}$. Then we can adjust $G$ by removing the edges $\backslash left\; \backslash \{\; S,\; D\_j\; \backslash right\; \backslash \}$ and $\backslash left\; \backslash \{\; T\_i,\; W\; \backslash right\; \backslash \}$, and adding the edges $\backslash left\; \backslash \{\; S,\; T\_i\; \backslash right\; \backslash \}$ and $\backslash left\; \backslash \{\; W,\; D\_j\backslash right\; \backslash \}$. This modification preserves the degree sequence of $G$, but the vertex $S$ is now adjacent to $T\_\{i\}$ instead of $D\_\{j\}$. In this way, any vertex not connected to $S$ can be adjusted accordingly so that $S$ is adjacent to $T\_\{i\}$ while maintaining the original degree sequence $A$ of $G$. Thus any vertex not connected to $S$ can be connected to $S$ using the above method, and then we have the first case once more, through which we can obtain the degree sequence $A\text{'}$. Hence, $A$ is graphic if and only if $A\text{'}$ is also graphic.

Let $6,\; 3,\; 3,\; 3,\; 3,\; 2,\; 2,\; 2,\; 2,\; 1,\; 1$ be a nonincreasing, finite degree sequence of nonnegative integers. To test whether this degree sequence is graphic, we apply the Havel-Hakimi algorithm:

First, we remove the vertex with the highest degree — in this case, $6$ —  and all its incident edges to get $2,\; 2,\; 2,\; 2,\; 1,\; 1,\; 2,\; 2,\; 1,\; 1$ (assuming the vertex with highest degree is adjacent to the $6$ vertices with next highest degree). We rearrange this sequence in nonincreasing order to get $2,\; 2,\; 2,\; 2,\; 2,\; 2,\; 1,\; 1,\; 1,\; 1$. We repeat the process, removing the vertex with the next highest degree to get $1,\; 1,\; 2,\; 2,\; 2,\; 1,\; 1,\; 1,\; 1$ and rearranging to get $2,\; 2,\; 2,\; 1,\; 1,\; 1,\; 1,\; 1,\; 1$. We continue this removal to get $1,\; 1,\; 1,\; 1,\; 1,\; 1,\; 1,\; 1$, and then $0,\; 0,\; 0,\; 0,\; 0,\; 0,\; 0,\; 0$. This sequence is clearly graphic, as it is the simple graph of $8$ isolated vertices.

To show an example of a non-graphic sequence, let $6,\; 5,\; 5,\; 4,\; 3,\; 2,\; 1$ be a nonincreasing, finite degree sequence of nonnegative integers. Applying the algorithm, we first remove the degree $6$ vertex and all its incident edges to get $4,\; 4,\; 3,\; 2,\; 1,\; 0$. Already, we know this degree sequence is not graphic, since it claims to have $6$ vertices with one vertex not adjacent to any of the other vertices; thus, the maximum degree of the other vertices is $4$. This means that two of the vertices are connected to all the other vertices with the exception of the isolated one, so the minimum degree of each vertex should be $2$; however, the sequence claims to have a vertex with degree $1$. Thus, the sequence is not graphic.

For the sake of the algorithm, if we were to reiterate the process, we would get $3,\; 2,\; 1,\; 0,\; 0$ which is yet more clearly not graphic. One vertex claims to have a degree of $3$, and yet only two other vertices have neighbors. Thus the sequence cannot be graphic.

• Erdős–Gallai theorem

{{reflist}}

• {{citation

| last= Havel

| first= Václav

| authorlink =V. J. Havel

| year = 1955

| title = A remark on the existence of finite graphs

| language = Czech

| journal = Časopis pro pěstování matematiky

| volume = 80

| issue= 4

| pages = 477–480

| doi= 10.21136/CPM.1955.108220

| url = http://eudml.org/doc/19050

| doi-access = free

}}

• {{citation

| last = Hakimi | first = S. L. | authorlink = S. L. Hakimi

| journal = Journal of the Society for Industrial and Applied Mathematics

| mr = 0148049

| pages = 496–506

| title = On realizability of a set of integers as degrees of the vertices of a linear graph. I

| volume = 10

| year = 1962| issue = 3 | doi = 10.1137/0110037 }}.

• {{citation

| last= Shahriari

| first= Shahriar

| year = 2022

| title = Invitation to Combinatorics, Cambridge U. Press.

| language = English

}}

• West, Douglas B. (2001). Introduction to graph theory. Second Edition. Prentice Hall, 2001. 45-46.

{{DEFAULTSORT:Havel-Hakimi algorithm}}

Category:Graph algorithms