Definition of Degree

The degree of a vertex (v) in a graph (G), denoted by (d_G(v)), is the number of edges of (G) incident with (v), with each loop counting as two edges. (J.A. Bondy, Graph Theory)

Two fundamental results follow from this definition:

1. Handshaking Theorem: For any graph (G),

   [ \sum_{v \in V} d(v) = 2m ]

   where (m) is the number of edges. The proof is left as an exercise.

2. In any graph, the number of vertices of odd degree is even.

   Proof: The Handshaking Theorem implies that the sum of all degrees is even. Therefore, the number of vertices with odd degree must be even.

Degree Sequence

If a graph (G) has vertices (v_1, v_2, \ldots, v_n), the sequence ((d(v_1), d(v_2), \ldots, d(v_n))) is called a degree sequence of (G).

Let (\mathbf{d} = (d_1, d_2, \ldots, d_n)) be a non-increasing sequence of nonnegative integers. Then:

There exists a graph with degree sequence (\mathbf{d}) if and only if (\sum_{i=1}^n d_i) is even.

Proof: The forward direction follows directly from the Handshaking Theorem.

For the reverse direction, take (n) distinct vertices (v_1, v_2, \ldots, v_n). If (d_i) is even, add (d_i/2) loops to (v_i); if (d_i) is odd, add ((d_i - 1)/2) loops to (v_i). Since the sum of the sequence is even, there is an even number of odd degrees. Pair these vertices arbitrarily and connect each pair with an edge. The resulting graph has degree sequence (\mathbf{d}).

Graphic Sequence

In graph theory, we are often more interested in simple graphs. A non-increasing sequence (\mathbf{d} = (d_1, d_2, \ldots, d_n)) of nonnegative integers is called a graphic sequence if there exists a simple graph with that degree sequence.

If (\mathbf{d} = (d_1, d_2, \ldots, d_n)) is graphic and (d_1 \ge d_2 \ge \cdots \ge d_n), then (\sum_{i=1}^n d_i) is even and for (1 \le k \le n): [ \sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n \min{k, d_i} ]

Proof: The first term (k(k-1)) is the maximum possible sum of degrees among (k) vertices in a simple graph (complete graph), while the second term represents the maximum contribution from vertices outside the set to the degrees of these (k) vertices.

(Erdős and Gallai proved in 1960 that these conditions are also sufficient.)

Checking if a Sequence is Graphic

The following lemma provides a method to determine whether a given non-increasing sequence of nonnegative integers is graphic.

Let (\mathbf{d} = (d_1, d_2, \ldots, d_n)) be a non-increasing sequence of nonnegative integers. Define (\mathbf{d}') as: [ \mathbf{d}' = (d_2 - 1, d_3 - 1, \ldots, d_{d_1+1} - 1, d_{d_1+2}, \ldots, d_n) ] Then (\mathbf{d}) is graphic if and only if (\mathbf{d}') is graphic.

Proof: (⇐) If (G') is a simple graph with degree sequence (\mathbf{d}'), add a new vertex (v_1) and connect it to vertices (v_2, \ldots, v_{d_1+1}). The resulting simple graph (G) has degree sequence (\mathbf{d}).

(⇒) Suppose (G) is a simple graph with degree sequence (\mathbf{d}) and (d(v_i) = d_i). If (v_1) is adjacent exactly to (v_2, v_3, \ldots, v_{d_1+1}), then (G - v_1) (obtained by deleting (v_1) and all its incident edges) has degree sequence (\mathbf{d}'). Otherwise, define:

[ i_0 = \max{i \mid v_1v_i \in E(G)} > d_1 + 1 ] [ j_0 = \min{j \mid v_1v_j \notin E(G)} \le d_1 + 1 ]

Since (d_{j_0} \ge d_{i_0}), there exists a vertex (v_s) adjacent to (v_{j_0}) but not to (v_{i_0}) (otherwise (d_{i_0} \ge d_{j_0} + 1 > d_{j_0}), a contradiction). Define a new graph (G' = G - {v_1v_{i_0}, v_sv_{j_0}} + {v_1v_{j_0}, v_sv_{i_0}}). Then (G') has the same degree sequence as (G), but with a smaller (i_0) and larger (j_0). Repeating this process eventually yields a graph where (v_1) is adjacent to (v_2, \ldots, v_{d_1+1}).

This lemma shows that checking if a length-(n) sequence is graphic reduces to checking if a length-((n-1)) sequence is graphic.

Havel-Hakimi Algorithm

Input: A degree sequance (\mathbf{d}). Output: Whether (\mathbf{d}) is graphic, and if so, a simple graph with that degree sequence.

1. Initialize (E^{(0)} = \varnothing), (\mathbf{d}^{(0)} = (d_1, d_2, \ldots, d_n) = \mathbf{d}), and (V^{(0)} = (v_1, v_2, \ldots, v_n)).
2. Sort (\mathbf{d}^{(k-1)}) in non-increasing order to obtain (\mathbf{d}^{(k)}), and reorder (V^{(k-1)}) accordingly to obtain (V^{(k)}). If (d_1^{(k)} = 0), go to step 4. Otherwise, proceed to step 3.
3. Set: [ E^{(k)} = E^{(k-1)} \cup {v_1^{(k)} v_j^{(k)} \mid j = 2, \ldots, d_1^{(k)} + 1} ] [ \mathbf{d}^{(k)} = (0, d_2^{(k)} - 1, \ldots, d_{d_1^{(k)}+1}^{(k)} - 1, d_{d_1^{(k)}+2}^{(k)}, \ldots, d_n^{(k)}) ] Increment (k). If all entries in (\mathbf{d}^{(k)}) are nonnegative, go to step 2; otherwise, the original sequence is not graphic.
4. The graph (G = (V^{(k)}, E^{(k-1)})) has degree sequence (\mathbf{d}).

R Implementation of the Havel-Hakimi Algorithm

First, install the igraph package:

install.packages("igraph")
library(igraph)

The folowing function checks whether a sequence is graphic:

is_graphical(
  out.deg,          # Integer vector: for undirected graphs, the degree sequence; for directed graphs, the out-degree sequence
  in.deg = NULL,    # For undirected graphs, leave as NULL; for directed graphs, the in-degree sequence
  allowed.edge.types = c("simple", "loops", "multi", "all")  # Default is "simple" for graphic sequences; other options allow loops or multiple edges
)

For more details, see the igraph documentation: is_graphical

To create a graph from a given degree sequence, use:

realize_degseq(
  out.deg,
  in.deg = NULL,
  allowed.edge.types = c("simple", "loops", "multi", "all"),
  method = c("smallest", "largest", "index")
)

For more details, see the igraph documentation: realize_degseq