Graphical Sequences

A graphical sequence is a list of nonnegative integers that can be the degree sequence of a simple graph. In combinatorics, you use it to decide whether a set of vertex degrees can actually be built.

What is Graphical Sequences?

A graphical sequence in Combinatorics is a list of degrees that can be realized by some simple graph. That means there is a graph with exactly those vertex degrees, with no loops and no multiple edges.

The idea starts with a degree sequence, which is just the list of how many edges touch each vertex. A sequence becomes graphical only if those numbers can fit together as a real graph. For example, the sequence 3, 3, 2, 2, 2 can be graphical, while 4, 1, 1, 1, 1 is not, because one vertex would need to connect to everyone and still leave the other degrees impossible to satisfy.

The first quick check is the Handshaking Lemma. Since every edge contributes 2 to the total degree count, the sum of the sequence must be even. If the sum is odd, you can stop right away, because no simple graph can produce it.

Even sum is necessary, but not enough. A sequence can still fail to be graphical because the degree requests do not match up in a valid way. That is where the Havel-Hakimi algorithm comes in. You sort the list from largest to smallest, remove the largest number, and then subtract 1 from the next largest terms that many times. If you ever get a negative number, the sequence is not graphical. If you can reduce everything to zeros, the sequence is graphical.

This is also where special graph families show up. A complete graph on n vertices has degree sequence n minus 1 repeated n times. A k-regular graph has every vertex degree equal to k, so its degree sequence is just k repeated over and over. Bipartite graphs add another layer, because the degrees have to fit a split between two vertex sets, not just any random arrangement.

So when you see a graphical sequence problem, you are not just checking arithmetic. You are checking whether a list of degree demands can be turned into an actual network of edges without breaking the rules of simple graphs.

Why Graphical Sequences matters in COMBINATORICS

Graphical sequences sit right at the point where counting meets structure in Combinatorics. A lot of graph theory problems ask not just how many edges there are, but whether a proposed pattern of connections can exist at all.

That makes this term useful anytime you are building or checking a graph from data. If a problem gives you vertex degrees and asks whether a graph is possible, the graphical sequence test is the move you use. If the sequence fails, you know the graph cannot exist, even if the numbers look reasonable at first glance.

It also connects to special graph families. Complete graphs and regular graphs have very predictable degree sequences, so graphical sequences help you recognize them quickly. For bipartite graphs, the degree list can hint at whether a split into two parts could work, especially when one side would need too many connections for the other side to support.

This concept also shows up in reconstruction-style questions. Instead of drawing the graph first, you start from the degrees and work backward. That is a useful shift in combinatorics because it trains you to move from pattern to structure, not just from picture to count.

How Graphical Sequences connects across the course

Degree Sequence

A graphical sequence is a degree sequence that actually comes from a simple graph. Not every degree sequence works, so the difference is between a list of numbers and a list that can be realized by edges. When you see a degree sequence problem, the question is often whether it is graphical or whether it describes a specific kind of graph.

Havel-Hakimi Algorithm

This is the standard procedure for testing whether a sequence is graphical. You repeatedly remove the largest degree and reduce the next largest degrees to match it, checking whether the list stays valid. In homework problems, Havel-Hakimi is the step-by-step way to prove a sequence works or fails instead of guessing from inspection.

Bipartite Graph

Bipartite graphs restrict where edges can go, so not every graphical sequence can come from one. If a sequence is supposed to match a bipartite graph, the degrees have to fit across two vertex sets with no edges inside a set. That makes the realization problem more constrained than for general simple graphs.

k-regular graph

A k-regular graph has the same degree at every vertex, so its degree sequence is a repeated k. That makes regular graphs one of the easiest cases to recognize inside graphical sequence problems. You still need the degree pattern to be possible for the chosen number of vertices, but the structure is much more uniform.

Is Graphical Sequences on the COMBINATORICS exam?

A problem set or quiz question will usually give you a list of degrees and ask whether it is graphical, or ask you to build a graph from the sequence. You start with a fast parity check using the Handshaking Lemma, then use Havel-Hakimi if the sum is even and the answer is not obvious. If the sequence is graphical, you may also need to identify a matching special graph, like a complete graph or a regular graph.

On written work, the main skill is showing the reduction clearly. Sort the sequence, subtract carefully, and watch for a negative entry or a list that reduces to all zeros. A lot of mistakes come from skipping the sort step or forgetting that simple graphs do not allow loops or repeated edges. If the problem asks for a graph, your final drawing should match every degree exactly, not just most of them.

Graphical Sequences vs Degree Sequence

A degree sequence is just the list of vertex degrees. A graphical sequence is a degree sequence with an extra condition, it can actually be realized by a simple graph. So every graphical sequence is a degree sequence, but not every degree sequence is graphical.

Key things to remember about Graphical Sequences

• A graphical sequence is a list of degrees that can come from a simple graph.

• The sum of the degrees must be even, because each edge contributes to two vertices.

• Havel-Hakimi is the main algorithm for checking whether a sequence is graphical.

• Complete graphs and regular graphs have very recognizable graphical sequences.

• If a sequence cannot be realized, the problem is not about drawing skill, it is about structure.

Frequently asked questions about Graphical Sequences

What is Graphical Sequences in Combinatorics?

It is a degree list that can actually be made into a simple graph. In other words, the numbers can be assigned to vertices so that each vertex has exactly that many edges. If the list fails the simple checks or Havel-Hakimi reduction, it is not graphical.

How do you tell if a sequence is graphical?

First check that the sum of the degrees is even. Then use Havel-Hakimi, which reduces the largest degree against the next largest degrees. If the process ends in all zeros, the sequence is graphical. If you get a negative number or an impossible list, it is not.

What is the difference between a degree sequence and a graphical sequence?

A degree sequence is any list of vertex degrees. A graphical sequence is one that can be realized by a simple graph. That extra realization condition is the whole point, because some degree lists look fine numerically but cannot actually happen in a graph.

Can a graphical sequence describe a complete graph or regular graph?

Yes. A complete graph on n vertices has degree sequence n minus 1 repeated n times, and a k-regular graph has degree sequence k repeated for every vertex. These are easy examples of graphical sequences because the pattern is very uniform and easy to check.