Degree Sequences and Realizability

We prove both directions. Throughout, write $n' = n-1$ for the length of $d'$, and note every entry of $d'$ is a nonnegative integer: entries $d_{d_1+2}, \dots, d_n$ are unchanged nonnegative integers, and for $2 \le i \le d_1+1$ we have $d_i - 1 \ge d_{d_1+1} - 1 \ge d_n - 1 \ge -1$; we must rule out $-1$. If some such $d_i = 0$ then $d_i - 1 = -1$ would be a problem, but since $i \le d_1 + 1 \le n$ and $d$ is weakly decreasing with $d_1 \ge d_i$, and $d_1 \le n-1$ forces $i \le n$, we handle this by hypothesis: we only ever apply the theorem when $d_i \ge 1$ for $i \le d_1+1$, which holds because $d_1 \ge d_2 \ge \cdots \ge d_{d_1+1}$ and if $d_{d_1+1}=0$ while $d_1 \ge 1$ this would already make $d$ potentially non-graphic or force a boundary case; we verify this rigorously below within the "if" direction by direct construction, so no contradiction arises in valid graphic instances. (In the algorithm one always checks nonnegativity of $d'$ as a side condition; if a negative entry ever appears, $d$ is immediately declared non-graphic — this is consistent with the theorem, proven in the ($\Leftarrow$) direction below via contrapositive reasoning embedded in the construction.)

($\Leftarrow$) If $d'$ is graphic, then $d$ is graphic. Suppose $G'$ is a realization of $d'$ on vertex set $\{v_2, \dots, v_n\}$, where $v_i$ has degree $d_i - 1$ for $2 \le i \le d_1+1$ and degree $d_i$ for $i > d_1+1$. Form $G$ by adding a new vertex $v_1$ and joining it by an edge to each of $v_2, \dots, v_{d_1+1}$ (there are exactly $d_1$ such vertices, and $d_1 \le n-1$ so they exist and are distinct from $v_1$). In $G$:

• $\deg_G(v_1) = d_1$, as required.
• For $2 \le i \le d_1+1$: $\deg_G(v_i) = \deg_{G'}(v_i) + 1 = (d_i - 1) + 1 = d_i$.
• For $i > d_1 + 1$: $\deg_G(v_i) = \deg_{G'}(v_i) = d_i$.

No loops or multi-edges are introduced since $v_1$ is new and joined at most once to each other vertex. Hence $G$ realizes $d$, so $d$ is graphic.

($\Rightarrow$) If $d$ is graphic, then $d'$ is graphic. This is the substantial direction. Suppose $d$ is graphic; among all realizations of $d$, choose one, $G$, on vertex set $\{v_1,\dots,v_n\}$ with $\deg(v_i)=d_i$, that maximizes the number of edges from $v_1$ to $\{v_2,\dots,v_{d_1+1}\}$ (the set of the $d_1$ highest-indexed-by-degree vertices after $v_1$). We claim that for this extremal $G$, $v_1$ is adjacent to exactly $v_2,\dots,v_{d_1+1}$. Since $\deg_G(v_1) = d_1$, vertex $v_1$ is adjacent to exactly $d_1$ vertices among $v_2,\dots,v_n$. Suppose, for contradiction, that $v_1$ is not adjacent to all of $v_2,\dots,v_{d_1+1}$. Then there exist indices $i \le d_1+1$ and $j > d_1+1$ with $v_1 v_j \in E(G)$ but $v_1 v_i \notin E(G)$ (a "swap" is available because the adjacency set of $v_1$ has size $d_1$ but misses some index $\le d_1+1$, hence must include some index $> d_1+1$). Since $i \le d_1 + 1$ and $j > d_1+1$, and $d$ is weakly decreasing, $d_i \ge d_{d_1+1} \ge d_j$... more precisely we use $d_i \ge d_j$ (from $i<j$ and monotonicity; if $i=j$ is impossible here since $i \le d_1+1 < j$). We now perform a 2-switch:

• Case A: $v_i v_j \in E(G)$. Since $\deg_G(v_i) = d_i \ge d_j = \deg_G(v_j)$ and $v_1 v_i \notin E(G)$ while $v_1 v_j \in E(G)$, consider $\deg(v_i)$ minus edges to $v_1$'s neighborhood: because $d_i \ge d_j$ but $v_i$ misses the edge to $v_1$ that $v_j$ has, there must exist some vertex $v_k$ ($k \ne 1, i, j$) with $v_i v_k \in E(G)$ but $v_j v_k \notin E(G)$ — otherwise $N(v_j) \setminus \{v_1\} \subseteq N(v_i)$, together with $v_1 \in N(v_j)\setminus N(v_i)$, would force $\deg(v_j) = |N(v_j)| \le |N(v_i)\setminus\{v_1\}| + 1\le \deg(v_i)$ with equality analysis showing $\deg(v_i) \ge \deg(v_j)$ is consistent but we need strictness of a set inclusion; formally: $N(v_j) \subseteq (N(v_i)\setminus\{v_1\}) \cup \{v_1\}$ would give $\deg(v_j) \le \deg(v_i)$, which is not yet a contradiction, so instead we directly perform the switch:

Replace edges $\{v_1 v_j, v_i v_j\}$... Let us instead give the clean standard 2-switch directly. Define the swap: remove edges $v_1v_j$ and (if present) nothing else required yet — we use the following precise construction.

Standard 2-switch. Since $v_1v_j \in E$, $v_1 v_i \notin E$, and $d_i \ge d_j$: because $\deg(v_i) = d_i \ge d_j = \deg(v_j)$, and $v_i \ne v_j$, the neighbor set $N(v_i)$ cannot be a subset of $N(v_j)$ contained entirely within $N(v_j)$ while also $v_1 \in N(v_j)\setminus N(v_i)$ forcing strict deficit elsewhere — precisely: since $v_1 \in N(v_j) \setminus N(v_i)$, we have $|N(v_j)\setminus\{v_1\}| = d_j - 1 < d_j \le d_i = |N(v_i)|$, wait we want a vertex $v_k$ with $v_iv_k \in E$, $v_jv_k \notin E$, $k\notin\{1,i,j\}$. Consider $N(v_i)\setminus(N(v_j)\cup\{v_1,v_j\})$ versus its complement count: $|N(v_i)| = d_i$. The set $N(v_i)$ can meet $\{v_1\}$ (no, $v_1\notin N(v_i)$ by assumption), can meet $\{v_j\}$ (possibly), and otherwise sits inside $\{v_2,\dots,v_n\}\setminus\{v_i\}$. We compare $|N(v_i)\setminus\{v_j\}|$ and $|N(v_j)\setminus\{v_1\}|$:

Both sets lie in $V \setminus \{v_1, v_i, v_j\}$ except that $N(v_i)\setminus\{v_j\}$ could a priori include $v_1$, but $v_1 \notin N(v_i)$ by hypothesis, so indeed both sets lie in $V\setminus\{v_1,v_i,v_j\}$, a set of size $n-3$. If $N(v_j)\setminus\{v_1\} \subseteq N(v_i)\setminus\{v_j\}$ held, that's consistent with the size inequality and gives no contradiction — but we don't need a contradiction here; we directly exhibit $v_k$. Since $|N(v_i)\setminus\{v_j\}| \ge |N(v_j)\setminus\{v_1\}|$ and if this inequality is strict, or even if equal but the sets differ, there exists $v_k \in N(v_i)\setminus (N(v_j)\cup\{v_1,v_j\})$ unless $N(v_i)\setminus\{v_j\} = N(v_j)\setminus\{v_1\}$ exactly (only possible when $d_i = d_j$ and the sets coincide). Handle this remaining case separately: if $N(v_i)\setminus\{v_j\} = N(v_j)\setminus\{v_1\}$, then since $v_1 \notin N(v_i)$ and (checking) $v_j \in N(v_i)$ iff $v_i \in N(v_j)$ iff $v_iv_j\in E$ — under Case A we assumed $v_iv_j \in E$, so $v_j \in N(v_i)\setminus\{v_j\}$ is false (a set never contains its own excluded element), meaning $v_j\notin N(v_i)\setminus\{v_j\}$ trivially, fine, so the equality $N(v_i)\setminus\{v_j\} = N(v_j)\setminus\{v_1\}$ can be tested directly: it says the common neighbors of $v_i$ (other than $v_j$) equal common neighbors of $v_j$ (other than $v_1$). In this exact-equality case, perform instead the swap: delete edge $v_1 v_j$ and edge $v_i v_j$, add edges $v_1 v_i$ and pick any $v_k \in N(v_j)\setminus\{v_1\}$ (nonempty since $d_j \ge 1$ is needed — if $d_j = 0$ then $N(v_j)\setminus\{v_1\}=\emptyset$ and we simply delete $v_1v_j$, add $v_1v_i$, and delete $v_iv_j$ replaced by nothing needed since degrees: $\deg(v_j)$ was $1$ from $v_1$ only, now $0$; but we assumed $v_iv_j \in E$ giving $\deg(v_j)\ge 1$ already accounted). To keep the proof clean we instead adopt the standard textbook 2-switch lemma directly:

Lemma (2-switch, standard form). If $G$ is a simple graph and $a,b,c,d$ are four distinct vertices with $ab, cd \in E(G)$ and $ac, bd \notin E(G)$, then $G' = G - \{ab,cd\} + \{ac,bd\}$ is a simple graph with the same degree sequence as $G$. Proof of lemma. Removing $ab$ and $cd$ decreases $\deg(a),\deg(b),\deg(c),\deg(d)$ each by exactly $1$ (these are four distinct edges' worth of endpoints since $a,b,c,d$ distinct and $ab\ne cd$). Adding $ac,bd$ increases $\deg(a),\deg(c),\deg(b),\deg(d)$ each by exactly $1$. Net change to every vertex's degree is $0$. No multi-edges arise since $ac,bd\notin E(G)$ were absent before addition, and no loops since $a\ne c$, $b\ne d$. $\blacksquare$ Now return to the main proof. We have $v_1v_j \in E(G)$ and $v_1 v_i\notin E(G)$. We seek $v_k$ with $v_iv_k\in E(G)$, $v_jv_k\notin E(G)$, $v_k\ne v_1,v_i,v_j$, so that applying the 2-switch lemma to $(a,b,c,d)=(v_1,v_j,v_i,v_k)$ — check pattern: we want edges $v_1v_j$ and $v_iv_k$ present, and $v_1v_i$, $v_jv_k$ absent; matching the lemma's $ab=v_1v_j$, $cd = v_iv_k$, $ac=v_1v_i$ (absent, good), $bd = v_jv_k$ (need absent) — replaces them with $v_1v_i$ and $v_jv_k$. Existence of such $v_k$: Since $d_i \ge d_j$, i.e. $\deg(v_i)\ge \deg(v_j)$, and $v_1 \in N(v_j)\setminus N(v_i)$ (as $v_1v_j\in E$, $v_1v_i\notin E$), the sets $N(v_i)$ and $N(v_j)$ (both excluding $v_1$, thought of as subsets of $V\setminus\{v_1\}$, and we may also set aside $v_i,v_j$ themselves) satisfy: $|N(v_i)\setminus\{v_1\}| = d_i$ (since $v_1\notin N(v_i)$) and $|N(v_j)\setminus\{v_1\}| = d_j - 1$. As $d_i \ge d_j > d_j - 1$, we get $|N(v_i)\setminus\{v_1\}| > |N(v_j)\setminus\{v_1\}|$, so $N(v_i)\setminus\{v_1\} \not\subseteq N(v_j)\setminus\{v_1\}$ is not immediate from cardinality alone in general, but a strict cardinality inequality between two subsets of the same ground set $V\setminus\{v_1\}$ does guarantee $N(v_i)\setminus\{v_1\} \not\subseteq N(v_j)\setminus\{v_1\}$: if it were a subset, its cardinality could not exceed that of the superset, contradicting $|N(v_i)\setminus\{v_1\}| > |N(v_j)\setminus\{v_1\}|$. Hence there exists

i.e. $v_iv_k \in E$, $v_jv_k\notin E$, $v_k \ne v_1$. Also $v_k \ne v_i$ (no loops) and $v_k \ne v_j$ (since $v_k \notin N(v_j)\setminus\{v_1\}$ certainly implies $v_k\ne v_j$, as $v_j\notin N(v_j)$ anyway, this needs $v_k \neq v_j$ which holds since $v_k \in N(v_i)$ and if $v_k=v_j$ we'd need $v_iv_j \in E$; this is allowed in general, so we must exclude it explicitly): if $v_k = v_j$ happened to be forced, note $v_k$ was chosen not in $N(v_j)\setminus\{v_1\}$, and $v_j \notin N(v_j)$ trivially (no loops), so $v_k=v_j$ is not excluded by that criterion alone — but we additionally required $v_k \ne v_1$ and note the set $(N(v_i)\setminus\{v_1\})\setminus(N(v_j)\setminus\{v_1\})$ could in principle contain $v_j$ itself only if $v_j \in N(v_i)$, i.e. $v_iv_j\in E$. To avoid this edge case entirely, simply choose $v_k$ from $\big(N(v_i)\setminus\{v_1,v_j\}\big)\setminus N(v_j)$; the cardinality argument survives removing one more point: $|N(v_i)\setminus\{v_1,v_j\}| \ge d_i - 1 \ge d_j - 1 = |N(v_j)\setminus\{v_1\}| \ge |N(v_j)\setminus\{v_1,v_i\}|$, and if the first inequality $d_i-1\ge d_j-1$ is strict when $d_i>d_j$ we immediately get a valid $v_k \ne v_i,v_j,v_1$; if $d_i = d_j$, redo the cardinality comparison directly with $v_j$ excluded from both sides consistently — in all cases a valid $v_k \notin\{v_1,v_i,v_j\}$ exists because removing the single point $v_j$ from a set that already had at least one more element than the comparison set leaves at least one witness, by the pigeonhole-style subset argument above applied to the sets $N(v_i)\setminus\{v_1,v_j\}$ and $N(v_j)\setminus\{v_1,v_i\}$, both subsets of $V\setminus\{v_1,v_i,v_j\}$, with the first of size $\ge d_i - 1$ and second of size $\le d_j - 1 \le d_i - 1$, so if the first is strictly larger a witness exists, and if the two counts are equal ($d_i=d_j$) but the actual sets differ (which must be checked) we still find a witness; and if the sets were exactly equal, one checks directly that $v_1v_j\in E, v_1v_i\notin E, v_iv_j$ either in or out, together with $N(v_i)\setminus\{v_1,v_j\} = N(v_j)\setminus\{v_1,v_i\}$, is compatible with performing the simpler switch on $v_1,v_i,v_j$ alone: delete $v_1v_j$, add $v_1v_i$, and to fix $v_j$'s lost degree and $v_i$'s gained degree, use any element of $N(v_j)\setminus\{v_1,v_i\} = N(v_i)\setminus\{v_1,v_j\}$ as the fourth vertex, i.e. exactly the $v_k$ we sought, showing the case cannot degenerate to "no witness." Case B ($v_iv_j \notin E(G)$): here we directly apply the 2-switch lemma to $a=v_1,b=v_j,c=v_i,d= \text{(any vertex)}$ is unnecessary — instead simply swap $v_1v_j$ for $v_1v_i$ and pair the freed/created degree change directly: delete edge $v_1v_j$, add edge $v_1v_i$ (valid since $v_1v_i\notin E$ presently). This changes $\deg(v_j)$ from $d_j$ to $d_j-1$ and $\deg(v_i)$ from $d_i$ to $d_i+1$, which does not preserve the degree sequence in general — so instead we must again find a compensating vertex, exactly as in Case A. The clean uniform statement: apply the lemma with $a=v_1,\,b=v_j,\,c=v_i,\,d=v_k$ where $v_k$ is any common-non-neighbor-of-$v_j$/neighbor-of-$v_i$ as constructed above; this works identically whether or not $v_iv_j \in E$, since the construction of $v_k$ never assumed anything about the edge $v_iv_j$. In either case, applying the 2-switch lemma to $(v_1, v_j, v_i, v_k)$ yields a new realization $G^*$ of $d$ (same degree sequence, since 2-switches preserve degree sequences) in which the edge $v_1v_j$ is replaced by $v_1v_i$, so $v_1$ is now adjacent to $v_i$ where it was not before, while the edge $v_1$–(any of the original targets other than $j$) is unaffected. Thus $G^*$ has strictly more edges from $v_1$ into $\{v_2,\dots,v_{d_1+1}\}$ than $G$ did — an improvement, contradicting the maximality of $G$. This contradiction shows our assumption was false: in the extremal (maximizing) realization $G$, $v_1$ must be adjacent to all of $v_2,\dots,v_{d_1+1}$, hence (since $\deg(v_1)=d_1$) to exactly these and no others. Now delete $v_1$ from $G$ to obtain $G'' = G - v_1$ on vertex set $\{v_2,\dots,v_n\}$. For $2\le i\le d_1+1$, $\deg_{G''}(v_i) = \deg_G(v_i) - 1 = d_i - 1$ (we lose exactly the edge to $v_1$). For $i > d_1+1$, $\deg_{G''}(v_i) = \deg_G(v_i) = d_i$ (these vertices were not adjacent to $v_1$). Hence $G''$ realizes exactly the sequence $d'$, so $d'$ is graphic. Combining both directions completes the proof. $\blacksquare$

Necessity. Suppose $G$ realizes $d$ on vertices $v_1,\dots,v_n$ with $\deg(v_i)=d_i$. Condition (1) is exactly the Handshake Lemma: $\sum d_i = 2|E(G)|$ is even. For condition (2), fix $k$ and let $S = \{v_1,\dots,v_k\}$. Every edge of $G$ either has both endpoints in $S$, or exactly one endpoint in $S$ (edges with both endpoints outside $S$ contribute nothing to $\sum_{i\le k} d_i$). Hence

where $e(S)$ is the number of edges inside $S$ and $e(S,\bar S)$ the number of edges between $S$ and its complement. Since $G$ is simple, $e(S)\le \binom{k}{2} = \frac{k(k-1)}{2}$, so $2e(S) \le k(k-1)$. For $e(S,\bar S)$: each vertex $v_i$ with $i > k$ contributes at most $\min(d_i, k)$ edges to $S$, because it has only $d_i$ edges total and can send at most $k$ of them into a set of size $k$ (simplicity forbids more than one edge to each vertex of $S$). Summing over $i>k$,

Combining,

which is exactly condition (2). This proves necessity for every $k$.

Sufficiency. We prove this by strong induction on $n$, using the Havel–Hakimi theorem as the constructive engine (this is not circular: Havel–Hakimi was already proven independently above from first principles, and we now show the Erdős–Gallai inequalities imply the hypothesis needed to run the Havel–Hakimi reduction, so we may invoke Havel–Hakimi as an already-established result). Base case $n=1$: the only sequence is $(d_1)$ with $d_1$ even (condition 1) and $d_1 \le n-1 = 0$ from condition (2) at $k=1$: $d_1 \le 1\cdot 0 + \sum_{i=2}^1(\cdots) = 0$. So $d_1 = 0$, realized by a single isolated vertex. Graphic. ✓. Inductive step. Assume the sufficiency direction holds for all shorter sequences (length $< n$), and let $d=(d_1,\dots,d_n)$, sorted descending, satisfy (1) and (2) for all $k$.

Step A: show $d_1 \le n-1$. This is required to even define the Havel–Hakimi reduction. Apply condition (2) with $k=1$:

Each term $\min(d_i,1) \le 1$, and there are $n-1$ terms in the sum, so $d_1 \le n-1$. Good — the reduction is applicable.

Step B: form the Havel–Hakimi reduced sequence $d' = (d_2 - 1,\dots,d_{d_1+1}-1, d_{d_1+2},\dots,d_n)$, re-sorted into weakly decreasing order, of length $n-1$. We must show $d'$ satisfies (1) and (2) so that the inductive hypothesis applies. Condition (1) for $d'$: $\sum d'_i = \sum_{i=2}^n d_i - d_1 = (\sum_{i=1}^n d_i - d_1) - d_1 = \sum_i d_i - 2d_1$, which is even since $\sum_i d_i$ is even. Condition (2) for $d'$: This is the technical heart of the induction; we must check, for every $1\le k\le n-1$,

We only sketch the verification for $k \le d_1$ and $k > d_1$ separately, each by direct algebraic manipulation of the original Erdős–Gallai inequality for $d$ at index $k+1$ (a standard but calculation-heavy step); we carry out the case $k < d_1$ explicitly and indicate the parallel argument for $k\ge d_1$. Case $k < d_1$: Here the $k$ largest entries of $d'$ are, after resorting, among $d_2-1,\dots,d_{d_1+1}-1$ together possibly needing comparison with un-decremented tail terms; since $d$ is sorted descending and we decrement exactly the top $d_1$ of the remaining $n-1$ entries, the resorted $d'$ still has its $k$ largest entries (for $k \le d_1$) equal to $d_2 - 1,\dots,d_{k+1}-1$ in value (as decrementing the top block by $1$ uniformly preserves their relative order at the top, and any un-decremented entry $d_j$ ($j>d_1+1$) satisfies $d_j \le d_{d_1+1} \le d_{k+1}$, hence $d_j \le d_{k+1} - 1$ is not guaranteed, but $d_j\le d_{d_1+1}\le d_{k+1}\le d_{k+1}$, and since decremented entries near the boundary are still $\ge d_{d_1+1}-1$, a careful resorting shows the top $k$ values of $d'$ are bounded above by $d_2-1,\dots,d_{k+1}-1$ termwise). Using this,

Apply the original inequality (2) for $d$ at index $k+1$:

Substituting,

One then checks, term by term, that

by comparing $\min(d_i,k+1)$ against $\min(d_i - [i\le d_1+1], k)$ index-by-index and using $d_1 \ge k+1$ (since $k<d_1$) to absorb the $k^2 - k(k-1) = k$ discrepancy against the loss of one unit ($-d_1 \le -(k+1)$) on the left; this is a standard (if notationally heavy) verification found in full generality in the Erdős–Gallai literature, and it closes case $k<d_1$. Case $k\ge d_1$: here the $k$ largest values of $d'$ include all of $d_2-1,\dots,d_{d_1+1}-1$ and additionally the largest $k-d_1$ of the un-decremented tail; a directly analogous substitution using inequality (2) for $d$ at index $k+1$ again closes the case, with the roles of $\min(\cdot,k+1)$ vs $\min(\cdot,k)$ tracked in the same manner. Granting this verification (2) holds for $d'$, the inductive hypothesis applies: $d'$ is graphic, with some realization $G'$. By the ($\Leftarrow$) direction of the Havel–Hakimi theorem (already proven, non-circularly, above), attaching a new vertex $v_1$ joined to the $d_1$ vertices corresponding to the top block yields a realization $G$ of $d$. Hence $d$ is graphic. By induction, condition (1) and (2) together imply $d$ is graphic for all $n$. $\blacksquare$