Graph Degree Sequence

In the study of networks, one of the most fundamental descriptors is the degree sequence—a simple list of the number of connections each node possesses. This seemingly basic census of a graph's vertices raises a critical question: what can this list of numbers truly tell us about the network's underlying structure? Can any arbitrary list of integers represent a real network, and if so, does it serve as a unique fingerprint for that network's architecture? This article tackles these questions by exploring both the power and the profound limitations of the degree sequence.

The following chapters will guide you through this exploration. In "Principles and Mechanisms," we will uncover the fundamental rules that govern all valid degree sequences, including the Handshaking Lemma and the powerful Havel-Hakimi algorithm for testing a sequence's validity. Subsequently, in "Applications and Interdisciplinary Connections," we will examine how this numerical fingerprint is used to deduce graph properties, its role in solving classic problems like the search for Eulerian trails, and its surprising inability to resolve questions of Hamiltonicity, ultimately revealing its connections to other deep mathematical concepts.

Now that we have a feel for what a graph and its degree sequence are, let's roll up our sleeves and peek under the hood. Think of a degree sequence as a kind of summary or blueprint for a network. It tells you, for a group of $n$ individuals (vertices), how many friends (edges) each one has. But it's a very peculiar kind of blueprint. It doesn't show you who is connected to whom. It's just a list of numbers. So, our first great question is: can any list of numbers be the degree sequence of a simple graph? Can we just write down a shopping list of desired connections and expect a network to exist?

The answer, perhaps surprisingly, is no. The world of graphs is governed by some beautifully simple and rigid laws.

Before we even try to draw a graph, we can often tell if a degree sequence is impossible just by checking two fundamental rules.

The first is one of the most charming results in graph theory, often called the ​​Handshaking Lemma​​. It states that if you add up the degrees of all vertices in a graph, the result must be an even number. Why? Imagine a party. The degree of a person is the number of hands they shook. If you sum up all the handshakes counted by each person, you have counted every single handshake exactly twice—once for each person involved in the shake. Since every edge has two ends, the sum of degrees, $\sum d_i$, is simply twice the total number of edges, $m$. So, $\sum d_i = 2m$. It follows that the sum of degrees must always be even.

Consider a proposed degree sequence for a network of 7 nodes: $(6, 5, 4, 3, 2, 1, 0)$. The sum is $21$, an odd number. We can declare this sequence impossible without drawing a single line! There's no simple graph in the universe with this degree sequence. It violates the Handshake Lemma.

The second rule is even more basic; it's a simple reality check. In a ​​simple graph​​ with $n$ vertices—where no vertex can have an edge to itself and there's at most one edge between any two vertices—what is the maximum number of connections a single vertex can have? Well, it can connect to every other vertex, and there are $n-1$ of them. Therefore, no vertex can have a degree greater than $n-1$.

This single, obvious fact is incredibly powerful. If someone proposes the degree sequence $(8, 4, 3, 3, 2, 2, 1, 1)$ for a simple graph on $n=8$ vertices, you can immediately spot the fraud. The very first number, $8$, is a glaring impossibility. A vertex in an 8-vertex graph cannot be connected to 8 other vertices. This rule also helps us distinguish between simple graphs and ​​multigraphs​​, where multiple edges are allowed. A sequence like $(4, 4, 3, 1)$ for a 4-vertex graph is impossible for a simple graph (since the maximum degree is $4-1=3$), but it's perfectly fine for a multigraph, where you could have, for instance, two edges connecting the first two vertices.

So, a sequence passes our two initial checks: the sum is even, and no degree is too large. Does that guarantee it's the real deal? Is it "graphic"? Not necessarily. To be certain, we need a way to actually construct such a graph. This is where a clever, recursive procedure called the ​​Havel-Hakimi algorithm​​ comes into play.

Imagine you have a set of vertices, each with a number of "stubs" or connection points corresponding to its required degree. The algorithm's strategy is simple and greedy: let's satisfy the most demanding vertex first.

1. Take the vertex with the highest degree, let's call it $v_1$ with degree $d_1$.
2. Connect its $d_1$ stubs to the $d_1$ vertices with the next highest degrees.
3. Now, erase $v_1$ from the picture. We are left with a smaller problem: a new set of vertices with updated degree requirements (the ones we connected to $v_1$ now need one fewer connection).
4. If this new, smaller degree sequence is graphic, then the original one was too! We can keep repeating this process.

The process ends when we reach a state that is either trivially graphic (like a sequence of all zeros, which is just a collection of isolated points or trivially non-graphic (if we get a negative number, for instance).

Let's see this in action. Consider the degree sequence for the complete graph on 5 vertices, $K_5$, where every vertex is connected to every other vertex. Each of the 5 vertices has degree 4. So our starting sequence $S_0$ is $(4, 4, 4, 4, 4)$.

• ​​Step 1:​​ Take the first '4', remove it. We connect it to the other four vertices. Their required degrees drop by one. The new sequence, $S_1$, is $(3, 3, 3, 3)$.
• ​​Step 2:​​ We repeat. Take the first '3', remove it. Connect it to the other three. Their degrees drop. The new sequence, $S_2$, is $(2, 2, 2)$.
• ​​Step 3:​​ Repeat again. Take a '2', connect it to the other two. We get $(1, 1)$.
• ​​Step 4:​​ One last time. Take a '1', connect it to the other '1'. We get $(0)$.

Since we successfully reduced the sequence to all zeros, the original sequence $(4, 4, 4, 4, 4)$ is indeed graphic! The algorithm is like a set of Russian dolls; opening one reveals a smaller, properly formed doll inside. If at any point we find a malformed doll, the whole set is invalid. This algorithm gives us a definitive yes-or-no answer. For the truly curious, there is an even more powerful, though less intuitive, condition called the ​​Erdős-Gallai theorem​​, which provides a set of inequalities that a sequence must satisfy to be graphic. It acts as a kind of master theorem, ensuring that at every scale, the "demand" for connections from the highest-degree vertices doesn't exceed the "supply" of connections available in the rest of the graph.

We now have a powerful toolkit. We can check basic laws and run a definitive algorithm. But this brings us to a deeper, more philosophical question: what does the degree sequence truly tell us about a graph's structure? If I give you a valid degree sequence, have I given you a unique blueprint for a single, specific graph?

The answer is a fascinating and emphatic "no." A degree sequence is an ambiguous blueprint. Many different graphs can share the exact same degree sequence.

Consider the simple sequence $(2, 2, 2, 2, 2, 2)$. Every vertex wants exactly two connections. What could this look like? One obvious answer is a single, elegant 6-vertex ring, the cycle graph $C_6$. This graph has a notable property: it's ​​bipartite​​, meaning you can color its vertices with two colors, say red and blue, such that no two vertices of the same color are adjacent. But there's another, completely different graph with the same degree sequence: two separate triangles, $C_3 \cup C_3$! This graph is made of two disconnected cliques. And importantly, a triangle is an odd-length cycle, which means this graph is not bipartite.

So, the same degree sequence can describe a connected graph or a disconnected one, a bipartite graph or a non-bipartite one. The numbers tell you the local "sociability" of each vertex, but they don't tell you about the global community structure.

This ambiguity even seeps into our verification process. The Havel-Hakimi algorithm is a test for the existence of a graph, not a preservation of its properties. It's entirely possible to start with a degree sequence that comes from a perfectly ​​connected​​ graph, apply one step of the algorithm, and end up with a new sequence that can only be realized by a ​​disconnected​​ graph. For example, the sequence $(3, 2, 2, 1)$ can form a connected "diamond" graph. But one step of Havel-Hakimi reduces it to $(1, 1, 0)$, which must represent two connected points and one isolated point—a disconnected graph. The algorithm is a clever verification trick, but in its process of deconstruction, it can tear apart the very connectedness of the original structure it's testing.

To end our exploration of principles, let's look at one final, beautiful piece of symmetry. For any simple graph $G$, we can imagine its ​​complement​​, denoted $G^c$. The complement is a graph with the same vertices, but it has an edge exactly where the original graph $G$ didn't. It's a graph of the "non-connections."

There is a wonderfully direct relationship between the degree sequence of a graph and that of its complement. If a vertex $v$ has degree $d_i$ in a graph $G$ with $n$ vertices, it is connected to $d_i$ other vertices. The total number of other vertices is $n-1$. Therefore, in the complement graph $G^c$, vertex $v$ must be connected to all the vertices it wasn't connected to in $G$. Its degree in $G^c$ will be $(n-1) - d_i$.

This gives us a simple transformation. If $G$ has degree sequence $S_A = (d_1, \dots, d_n)$, then its complement $G^c$ has the degree sequence $S_B = (n-1-d_n, \dots, n-1-d_1)$ (we reverse the order because if $d_1$ is the largest degree in $S_A$, then $n-1-d_1$ will be the smallest in $S_B$). This relationship is not just a curiosity; it's a powerful tool. For instance, if we know the degree sequence of a graph, we can instantly calculate the total number of edges in its complement graph, without ever needing to see or draw either one!

From simple counting rules to recursive games and hidden symmetries, the degree sequence provides our first quantitative window into the intricate world of networks. It is a compact, yet surprisingly rich, description of structure, whose rules and limitations reveal the deep mathematical beauty governing all connections.

We have seen that a graph's degree sequence is a simple list of numbers, a sort of numerical census of its vertices. At first glance, it might seem like a rather dry and superficial summary. How much can a simple count of connections really tell us about the intricate web of relationships that a graph represents? Can this "fingerprint" uniquely identify a network, or is it merely a blurry shadow of the real thing?

As we shall now see, the answer is wonderfully complex. The degree sequence, despite its simplicity, is a surprisingly powerful key. It unlocks fundamental properties, helps us navigate networks, and even reveals deep and unexpected unities with other branches of mathematics. Our journey into its applications will be one of discovery, showing us both the remarkable power and the subtle limitations of this humble list of integers.

The most immediate secret the degree sequence reveals is the total number of connections in the entire network. This is thanks to a beautifully simple principle, often called the Handshaking Lemma. Imagine a party where the vertices are people and edges are handshakes. Each person's degree is the number of hands they've shaken. If we sum up these numbers across all people, what have we counted? We've counted each handshake exactly twice, once from each person involved. Therefore, the sum of all degrees must be exactly twice the number of edges.

This isn't just a party trick. Consider two separate online communities, each with its own network of friendships. If we have the degree sequence for each community, we can instantly calculate the total number of friendships within each. If we then consider the combined population as a single, disconnected network, the total number of friendships is simply the sum of the edges in the two original groups—a value we can find directly from their degree sequences without ever needing to see the graphs themselves. This elementary fact is the bedrock upon which many other insights are built.

But the degree sequence can tell us more than just a total count. It can reveal properties of more complex structures derived from the original graph. Let's imagine creating a new graph, not of the vertices, but of the connections themselves. This is called the ​​line graph​​, $L(G)$. In $L(G)$, each vertex represents an edge from our original graph $G$. Two vertices in $L(G)$ are connected if their corresponding edges in $G$ shared a common endpoint. Think of it as a map of "adjacent friendships" or "intersecting data links."

How many edges does this new, more abstract graph have? It seems like a complicated question. Yet, the answer is elegantly encoded within the original degree sequence. Consider a single vertex $v_i$ in $G$ with degree $d_i$. This vertex is the meeting point for $d_i$ different edges. Any pair of these edges share $v_i$ as a common endpoint, so their corresponding vertices in $L(G)$ will be connected. The number of such pairs is given by the simple combinatorial formula $\binom{d_i}{2}$. By summing this quantity over all vertices in the original graph, we get the total number of edges in the line graph: $|E(L(G))| = \sum_{i=1}^{n} \binom{d_i}{2}$. Once again, the degree sequence alone, without any visual map of the network, gives us a precise structural number. The simple list of degrees contains the seed of this higher-order structure.

With these tools, we can begin to play detective. Given only a degree sequence, can we deduce the fundamental nature of the network it came from? Sometimes, with a bit of logic, the answer is a surprising "yes."

Consider the degree sequence $(3, 3, 1, 1, 1, 1)$. We have $n=6$ vertices. Using our handshaking principle, the sum of degrees is $3+3+1+1+1+1=10$, which means the graph must have $m=5$ edges. Now, a fascinating fact in graph theory is that any connected graph with $n$ vertices and exactly $n-1$ edges must be a ​​tree​​—a network with no cycles. Our graph has $n=6$ and $m=5$. So, if it is connected, it must be a tree. Can we be sure it's connected? In this particular case, we can. A disconnected graph with these degrees would be impossible to construct (you can try!). Therefore, any simple graph with the degree sequence $(3, 3, 1, 1, 1, 1)$ is not just any graph; it must be a tree. The abstract sequence of numbers has forced a very specific and important global structure.

This deductive power has famous practical applications. Imagine designing a route for a snowplow in a city, or a path for a diagnostic packet to test every link in a computer network. The goal is to traverse every single edge (road or data link) exactly once. Such a path is called an ​​Eulerian trail​​. The magnificent discovery by Leonhard Euler in the 18th century was that the possibility of such a trail depends almost entirely on the degrees of the vertices. A network has an Eulerian trail if and only if it has either zero or exactly two vertices of odd degree (and all its edges are part of a single connected piece).

So, if an operations team has the degree sequence of their network, they can immediately check this "parity condition." It's a powerful first step. However, this also leads us to the first hint of the degree sequence's limitations. The sequence tells you about the parity, but it doesn't, by itself, guarantee that the network is connected. A network could have two odd-degree vertices but exist in two separate, disconnected pieces. No single trail could ever cover both. The degree sequence provides a crucial clue, but it doesn't tell the whole story.

This brings us to a critical question: if two graphs share the same degree sequence, are they necessarily the same graph (in the sense of being isomorphic)? The answer is a definitive ​​no​​. The degree sequence is not a complete invariant.

Perhaps the most famous problem where this limitation becomes starkly apparent is the search for ​​Hamiltonian cycles​​—a tour that visits every vertex exactly once before returning to the start. Unlike Eulerian trails, there is no simple degree-based criterion for Hamiltonicity. In fact, it's one of the great famously hard problems in computer science.

To see why the degree sequence is insufficient, consider the sequence $(6, 3, 3, 3, 3, 3, 3)$ on $n=7$ vertices. There are at least two completely different graphs that share this sequence. One is the ​​wheel graph​​ $W_7$, formed by a central hub connected to a 6-vertex rim. This graph is clearly Hamiltonian; you can simply tour the rim and then detour to the hub. The other graph is constructed by taking two complete graphs on four vertices ($K_4$) and fusing them at a single, shared vertex. The shared vertex has degree $3+3=6$, and the other $6$ vertices have degree $3$. This graph, however, is not Hamiltonian. The shared vertex is a "cut-vertex"; if you remove it, the graph falls apart into two pieces. No single cycle could possibly span such a structure.

Here we have two networks. An inventory of their parts—one vertex of degree 6, six vertices of degree 3—is identical. Yet their fundamental architecture is profoundly different. One is robustly connected, allowing for a grand tour, while the other is fragile. The degree sequence, in its focus on the individual, misses the crucial information about who is connected to whom.

This idea extends into deeper mathematical territory. Physicists and mathematicians often analyze graphs using tools from linear algebra, such as the ​​Laplacian matrix​​. The set of eigenvalues of this matrix, its "spectrum," serves as another, more sophisticated, fingerprint. Yet even this fingerprint is not perfect. There exist pairs of non-isomorphic graphs that are "cospectral"—they produce the same music, so to speak. Interestingly, it is possible to find two non-isomorphic, cospectral graphs that also happen to share the exact same degree sequence. This reinforces the lesson: capturing the full essence of a graph's structure is a subtle business, and the degree sequence is just one piece of a larger puzzle.

Just when we might start to think the degree sequence is too limited, it surprises us again. For certain special classes of graphs, the sequence holds far more information than usual, sometimes even uniquely defining the graph's structure.

One such class is that of ​​threshold graphs​​. These graphs can be thought of as modeling hierarchical networks. They are built up one vertex at a time, where each new vertex is either a "loner" (isolated, connected to no one) or a "socialite" (dominating, connected to everyone already present). It turns out that whether a given degree sequence can belong to a threshold graph is not a matter of guesswork. For some sequences, like $(4, 3, 2, 2, 1)$, not only does a threshold graph exist, but it is the only possible graph with that sequence. For this restricted, orderly world, the degree sequence is no longer a shadow but a complete blueprint.

The story culminates in a truly beautiful and unexpected connection between the world of networks and the abstract realm of number theory. The question, "Could this list of numbers be the degree sequence of a threshold graph?" finds its definitive answer in a property related to ​​integer partitions​​. A theorem states that a sequence is the degree sequence of a threshold graph if and only if it satisfies a special "Balance Condition." This condition involves finding a special point in the sequence, the "Staircase Index" $m$, which separates the high-degree "core" vertices from the low-degree "peripheral" ones. The condition then states that the sum of degrees in the core must perfectly balance the sum of degrees in the periphery, plus a term related to the size of the core itself: $\sum_{i=1}^{m} d_i = m(m-1) + \sum_{j=m+1}^{n} d_j$.

This is a profound result. A question about physical connections in a network is transformed into a pure, arithmetic identity. It reveals a hidden order, a mathematical unity that we would never suspect just by looking at nodes and edges. It is in these moments—when a simple idea like counting a vertex's neighbors leads us to deep structural truths and bridges to entirely different fields of thought—that we see the true beauty of mathematics. The humble degree sequence, it turns out, is not just an accounting tool; it is a gateway to a much larger universe of ideas.