Skip to main content

MA 415G course notes

Benjamin Braun

Section 3.6 Degree Sequences

We have seen that the degrees of the vertices play several key roles for graphs. This leads us to the following definition and theorem.
πŸ”—

Definition 3.6.1.

Given a finite graph \(G\text{,}\) the degree sequence of \(G\) is the sequence of vertex degrees of \(G\) written in non-increasing order. If a sequence \(\mathbf{d}=(d_1,d_2,\ldots,d_n)\) with \(d_1 \geq d_2 \geq \cdots \geq d_n\) is the degree sequence of a graph, then we say \(\mathbf{d}\) is a graphic sequence. Note that there might be more than one graph with the same graphic sequence.
πŸ”—
πŸ”—

Example 3.6.2.

The degree sequence of the following graph is \((7, 6, 6, 5, 5, 4, 3, 3, 3, 2)\text{.}\)
πŸ”—
Figure 3.6.3. Example for graph degree sequence
πŸ”—
πŸ”—

Checkpoint 3.6.4.

The main question we will ask about degree sequences is: which non-increasing lists of integers are graphic?
πŸ”—
We will start by investigating a special class of graphs called threshold graphs.
πŸ”—

Definition 3.6.5.

Consider the following two operations on a finite graph \(G\text{:}\)
  • Isolated addition (I): add a new vertex of degree zero to \(G\text{,}\) i.e., add an isolated vertex.
    πŸ”—
    πŸ”—
  • Suspension (S): add a new vertex that is connected by an edge to every vertex of \(G\text{;}\) the resulting graph is called the suspension of \(G\text{.}\)
    πŸ”—
    πŸ”—
A threshold graph is a graph obtained by starting with a single vertex and applying any sequence of isolated additions and suspensions.
πŸ”—
πŸ”—

Checkpoint 3.6.6.

For each of the following sequences (read from left to right) of isolated additions and suspensions, find the resulting threshold graph and calculate its degree sequence. Remember to start with a single vertex before you apply these operations!
  1. SSSSSS
    πŸ”—
    πŸ”—
  2. IIISIIIS (i.e., add three isolated vertices to the first isolated vertex, followed by a suspension, followed by adding three more isolated vertices, followed by another suspension)
    πŸ”—
    πŸ”—
  3. SISISIS
    πŸ”—
    πŸ”—
  4. SSSIISISS
    πŸ”—
    πŸ”—
πŸ”—
πŸ”—

Checkpoint 3.6.7.

For a threshold graph with \(n\) vertices with degree sequence \((d_1,d_2,\ldots,d_n)\text{,}\) explain why
\begin{equation*} d_1 = \sum_{j=2}^n\min(1,d_j) \, . \end{equation*}
πŸ”—
πŸ”—

Checkpoint 3.6.8.

For a threshold graph with \(n\) vertices with degree sequence \((d_1,d_2,\ldots,d_n)\) and \(d_2\geq 1\text{,}\) explain why
\begin{equation*} d_1 + d_2 = 2 + \sum_{j=3}^n\min(2,d_j) \, . \end{equation*}
Hint: Think about counting the vertex-edge adjacencies for each edge adjacent to \(v_1\) or \(v_2\text{.}\)
πŸ”—
πŸ”—
These observations lead us to the following property of threshold graphs.
πŸ”—

Definition 3.6.9.

Given a graphic degree sequence \(\mathbf{d}=(d_1,d_2,\ldots,d_n)\text{,}\) the corrected Durfee number is
\begin{equation*} m=m(\mathbf{d})= |\{j:d_j\geq j-1\}| \, . \end{equation*}
πŸ”—
πŸ”—

Checkpoint 3.6.10.

Checkpoint 3.6.12.

Write out each of these equalities for \(n=6\) and \(k=1,2,3,4,5\text{.}\)
πŸ”—
πŸ”—
We start with the following lemma. We write \(N_G(v)\) or \(N(v)\) to denote the set of vertices in \(G\) that are adjacent to \(v\text{,}\) i.e., connected to \(v\) by an edge. This set is called the neighbors of \(v\text{.}\)
πŸ”—

Proof.

We prove this by induction on the number of vertices in \(G\text{.}\) If there are one or two vertices, then this is true since the sets under consideration are empty. Now, suppose that \(G'\) is a threshold graph on \(n\) vertices for which the lemma holds. When we add a vertex to \(G'\text{,}\) resulting in a graph \(G\) with one more vertex, then this can either happen through an isolated vertex or suspension move. If an isolated vertex is added, then none of the neighborhoods of the vertices change, and the new vertex (having degree zero) is labeled as \(v_{n+1}\text{,}\) so the result holds since it already holds for \(G'\text{.}\)
πŸ”—
If a suspension vertex is added, then the new vertex has degree \(n\) and is labeled \(v_1\text{,}\) while all other vertices have their degrees increased by one and their labels are each increased by one. As \(v_1\) is added to the neighborhood of every existing vertex, then since \(N_{G'}(v_j)\) consists of the first \(s\) vertices from the list for \(G'\text{,}\) and the new \(v_1\) is a neighbor in \(G\) of every vertex in \(G'\text{,}\) we have that the claim regarding the initial segment of vertices being neighbors also holds in \(G\text{.}\)
πŸ”—
πŸ”—

Checkpoint 3.6.14.

Let \(G\) be the threshold graph obtained via the construction SSSIISISS
  1. Verify that this lemma holds for \(G\) .
    πŸ”—
    πŸ”—
  2. Go through the induction step in the proof of the lemma above starting from \(G\text{.}\)
    πŸ”—
    πŸ”—
πŸ”—
πŸ”—

Proof of TheoremΒ 3.6.11.

To prove that a threshold graph \(G\) on \(n\) vertices satisfies
\begin{equation*} \sum_{i=1}^k d_i = k(k-1) + \sum_{j=k+1}^n \min(k,d_j) \end{equation*}
for every \(1\leq k\leq m(\mathbf{d})\text{,}\) we will count the quantity \(\sum_{i=1}^k d_i\) in two ways. First, observe that \(\sum_{i=1}^k d_i\) counts the number of vertex-edge pairs \((v,e)\) where \(v\in \{v_1,\ldots,v_k\}\) and \(v\) is incident to \(e\text{.}\)
πŸ”—
Second, since \(k\leq m(\mathbf{d})\text{,}\) we have that \(d_i\geq i-1\) for all \(i\leq k\text{,}\) and thus \(v_1,\ldots,v_{i-1}\) are all neighbors of each such \(v_i\text{.}\) Thus, the first \(k\) vertices in \(G\) form a complete graph, which has \(k(k-1)/2\) edges, leading to \(k(k-1)\) vertex-edge pairs. Each vertex \(v_j\) for \(j\geq k+1\) is connected to the first \(d_j\) vertices in \(G\text{.}\) If \(d_j\geq k\text{,}\) then this corresponds to \(k\) vertex-edge adjacencies involving a vertex in \(\{v_1,\ldots,v_k\}\text{.}\) If \(d_j\lt k\text{,}\) then this corresponds to \(d_j\) such adjacencies. Thus, the left-hand and right-hand side of the equality both enumerate the same set, and thus are equal.
πŸ”—
πŸ”—

Checkpoint 3.6.15.

What is remarkable about threshold graphs is that they are the most extreme you can get with regard to these numerical relationships for degree sequences. Specifically, the following theorem due to ErdΕ‘s and Gallai (which we will state without proof) characterizes graphical degree sequences by relaxing the equalities that we have been investigating.
πŸ”—

Checkpoint 3.6.17.

There is another beautiful recursive characterization of degree sequences. We call a sequence \((d_1,d_2,\ldots,d_n)\) a proper sequence if
\begin{equation*} n-1\geq d_1\geq d_2\geq \cdots \geq d_n \geq 0 \, . \end{equation*}
πŸ”—

Example 3.6.19.

Starting with the proper sequence \(\mathbf{d}=(5,3,3,2,2,2,2)\text{,}\) we can apply a Havel-Hakimi step in position \(1\text{.}\) We first delete \(d_1=5\) to obtain \((3,3,2,2,2,2)\text{,}\) then we subtract one from each of the first five entries to obtain to obtain the sequence \((2,2,1,1,1,2)\text{.}\) We then rearrange this to obtain the proper sequence \((2,2,2,1,1,1)\text{.}\) Thus, by the Havel-Hakimi theorem, \((5,3,3,2,2,2,2)\) is graphic if and only if \((2,2,2,1,1,1)\) is graphic.
πŸ”—
πŸ”—

Checkpoint 3.6.20.

Proof.

We first prove that if \(\mathbf{c}\) is graphic, then so is \(\mathbf{d}\text{.}\) Suppose \(\mathbf{c}\) is a graphic sequence, i.e., there is a graph that realizes the degree sequence \(\mathbf{c}\text{.}\) Suppose \(i_1,\ldots,i_k\) are the indices of the entries that had their degree dropped when \(d_i\) was removed. Starting with a graph \(G_{\mathbf{c}}\) with degree sequence \(\mathbf{c}\text{,}\) add a new vertex and connect it to the vertices having degrees \(c_{i_r}\) for \(1\leq r\leq k\text{.}\) This produces a graph with degree sequence \(\mathbf{d}\text{.}\)
πŸ”—
We next prove that if \(\mathbf{d}\) is graphic, then so is \(\mathbf{c}\text{.}\) Our first goal is to show that, much like the case of threshold graphs, if \(\mathbf{d}\) is graphic then there is a graph realizing \(\mathbf{d}\) such that a vertex of degree \(d_i\) is connected to the \(d_i\) vertices of highest degrees. Let \(G\) be a graph with degree sequence \(\mathbf{d}\text{.}\) Relabel the vertex set of \(G\) as \(\{v_1,\ldots,v_n\}\) such that \(d_i=\deg(v_i)\text{.}\) We say that \(j\) and \(k\) are a missing pair if there is an \(i\) so that \(v_j\) is adjacent to \(v_i\text{,}\) \(v_k\) is not adjacent to \(v_i\text{,}\) and \(d_j\lt d_k\text{.}\) In other words, there is a neighbor of \(v_i\) with strictly smaller degree than some non-neighbor of \(v_i\text{.}\) If we have a missing pair, then there must be a fourth vertex \(v_t\) that is a neighbor of \(v_k\) but not of \(v_j\text{.}\) We can then delete from \(G\) the edges
\begin{equation*} \{v_i,v_j\} \text{ and } \{v_k,v_t\} \end{equation*}
and replace them with the edges
\begin{equation*} \{v_i,v_k\} \text{ and } \{v_j,v_t\} \, . \end{equation*}
This yields a new graph with degree sequence \(\mathbf{d}\) and one less missing pair than \(G\text{.}\) Iterating this process, we eventually reach a graph \(H\) realizing \(\mathbf{d}\) that has no missing pairs. If \(d_i\) is the entry removed by the Havel-Hakimi step, then removing vertex \(v_i\) from \(H\) removes one edge from each of the highest degree vertices in \(H\text{,}\) which yields a graph realizing the degree sequence \(\mathbf{c}\text{,}\) as desired.
πŸ”—
πŸ”—
The Havel-Hakimi theorem gives rise to an algorithm to test whether or not a proper sequence is graphic. Remember that \((d_1,d_2,\ldots,d_n)\) is a proper sequence if
\begin{equation*} n-1\geq d_1\geq d_2\geq \cdots \geq d_n \geq 0 \, . \end{equation*}
πŸ”—

Example 3.6.22.

Consider the sequence \((5,5,5,5,2,1)\) with \(N=6\text{.}\) We can apply a Havel-Hakimi step in position \(1\) to obtain \((4,4,4,1,0)\text{,}\) which is a proper sequence. We can then apply a Havel-Hakimi step in position \(5\) to obtain \((4,4,4,1)\text{,}\) which is not a proper sequence since \(n=4\) and \(d_1=4\gt 3\text{.}\) Thus, by the Havel-Hakimi test, \((5,5,5,5,2,1)\) is not graphic.
πŸ”—
πŸ”—

Checkpoint 3.6.23.

πŸ”—
PrevTopNext