Basic explanation of Havel-Hakimi

Question

I am having a little bit of difficult understanding the Havel-Hakimi theory/algorithm.

Could someone explain this theorem to me in hopefully basic terms. For example, what is $d_{d_{1}+2}$ ?

Answer 1

Like @saulspatz mentionend: the sequence is a decreasing list of integers. It's called graphic if those integers correspond to the degrees of vertices in a simple graph $G$ with $d_i=|\delta_G(v_i)|$.

e.g. (1,0), (2,1,0) are not graphic, but (1,1), (3,1,1,1) are graphic.

$"\impliedby"$ $(d_2 - 1, d_3 -1,...,d_{d_1 + 1} - 1,d_{d_1 + 2},...,d_n)$ is graphic implies $(d_1, d_2,...,d_n)$ to be graphic. Just add a new vertex and add edges conntecting it to the vertices corresponding to $d_2-1, d_3-1,...$

$"\implies"$ $(d_1, d_2,...,d_n)$ is graphic. Let $G$ be a simple graph such that its degree sequence is exactly this list and let $v_i$ be the vertex with $|\delta(v_i)|= d_i$. Get new simple Graph $G'$ by removing $v_1$ from $G$. If now the sequence is equal to $(d_2 - 1, d_3 -1,...,d_{d_1 + 1} - 1,d_{d_1 + 2},...,d_n)$ we are done. But that doesn't necessarily have to be the case.

So in case it is not: there is a $j\in \{2,...,d_1+1\}$ with $|\delta_{G'}(v_j)|=d_j \neq d_j-1$. Hence $\{v_1,v_j\}\notin E(G)$. But then there has to be a $k\in \{d_1+2,...,n\}$ with $\{v_1,v_k\}\in E(G)$ and so $|\delta_{G'}(v_k)|= d_k - 1$. Take $w\in\delta (v_j)$ with $e:=\{ w,v_k\}\notin E(G)$. This neighbor $w$ of $v_j$ has to exist. If not $d_j < d_k \implies \unicode{x21af}$.

Add $e$ to $G'$ and remove $\{v_j,w\}$ from $G'$ $\implies|\delta_{G'}(v_j)|=d_j-1$ and $|\delta_{G'}(v_k)|=d_k$ $\tag*{$\Box$}$