Diagnosing Nongraphic Sequences

When a Candidate Sequence Cannot Be a Degree Sequence

A list of nonnegative integers may look plausible as a collection of vertex degrees and still be impossible to realize in a simple graph. Some failures are immediate: a degree might be too large for the number of available neighbors, or the sum of the entries might be odd. Other sequences pass those quick checks but fail after one or more Havel–Hakimi reductions. The aim here is to use each failure as a specific certificate of nongraphicality.

Definition: A finite sequence of nonnegative integers \(d_1,d_2,\dots,d_n\) is graphical if there is a finite simple graph with \(n\) vertices whose vertex degrees, counted with multiplicity, are exactly those integers. A sequence that is not graphical is nongraphic. We usually write a candidate in nonincreasing order, \(d_1\ge d_2\ge\cdots\ge d_n\). Reordering entries does not change whether the sequence is graphical.

The empty sequence is graphical: it is realized by the graph with no vertices. For a nonempty sequence, graphicality concerns an actual simple graph, so every entry must be a nonnegative integer. In particular, a negative entry is not a possible vertex degree.

Quick Necessary Tests

Before applying a reduction, check the entries and their sum. In a simple graph on \(n\) vertices, a vertex can be adjacent to at most the other \(n-1\) vertices. Also, every edge contributes exactly two to the sum of all vertex degrees, one at each endpoint. These facts give basic rejection tests.

Proposition: If \((d_1,\dots,d_n)\) is graphical, then each \(d_i\) is an integer with \(0\le d_i\le n-1\), and \(\sum_{i=1}^n d_i\) is even.

Proof. In a simple graph, degrees count incident edges, so they are nonnegative integers. A vertex has no loop and cannot have more than one edge to each of the other \(n-1\) vertices, which gives \(d_i\le n-1\). For the sum, count the incidences between vertices and edges in two ways. Each vertex contributes its degree, so the count is \(\sum_{i=1}^n d_i\). Each edge has exactly two endpoints, so the same count is \(2|E|\). Therefore \(\sum_{i=1}^n d_i=2|E|\), an even number. \(\square\)

These are necessary conditions: every graphical sequence satisfies them. They are not, by themselves, sufficient. In particular, an even sum does not guarantee that the requested degrees can be joined up without violating the rules of a simple graph.

Worked Example: Immediate Failures

Consider the candidate lists \((4,2,2,0)\) and \((3,2,-1)\). For the first list, \(n=4\), so a vertex can have degree at most \(n-1=3\). Its entry \(4\) exceeds that bound, so the list is nongraphic. Its sum is \(4+2+2+0=8\), which is even; the parity test does not repair the excessive degree.

The second list contains \(-1\). A degree counts incident edges and cannot be negative, so this list is nongraphic without any reduction. Its sum is \(3+2+(-1)=4\), also even, which again shows that evenness alone cannot certify graphicality.

Check: The first list fails the simple-graph bound \(4\le3\), and the second fails nonnegativity \(-1\ge0\). Each failure contradicts a necessary condition proved above.

Havel–Hakimi as a Rejection Test

When the quick tests do not settle the question, sort the sequence in nonincreasing order and perform a Havel–Hakimi reduction. Remove the largest entry \(d_1\), then subtract \(1\) from each of the next \(d_1\) entries. Sort the resulting list again before continuing. If \(d_1\) exceeds the number \(n-1\) of remaining entries, the reduction cannot be performed. If a subtraction produces a negative entry, the resulting list cannot be graphical.

Theorem (Havel–Hakimi reduction): Let \(d_1\ge d_2\ge\cdots\ge d_n\) be nonnegative integers, with \(n\ge1\) and \(d_1\le n-1\). Form the list by removing \(d_1\), subtracting \(1\) from \(d_2,\dots,d_{d_1+1}\), leaving the other entries unchanged, and sorting the result. The original sequence is graphical if and only if the resulting sequence is graphical. If a subtraction gives a negative entry, the original sequence is nongraphic. The reduction theorem was proved in the earlier material on Havel–Hakimi reduction.

The theorem is an equivalence, not just a way to find possible realizations. It means that a failed reduction proves the original sequence is nongraphic; it also means that reductions ending in zeros certify graphicality. The process stops when it encounters a negative entry, an impossible excessive largest entry, or a list of zeros. A list of zeros is realized by an edgeless graph on the corresponding number of vertices.

Consequence: If a Havel–Hakimi process produces a negative entry, the original candidate sequence is nongraphic.

Proof. At every reduction with a nonnegative resulting list, the Havel–Hakimi theorem says the current list is graphical exactly when the reduced list is graphical. Applying this equivalence successively preserves the answer at each step. A list containing a negative entry is not graphical, because degrees in a simple graph are nonnegative. Therefore, if a reduction produces a negative entry, the current list is nongraphic; the equivalences at all earlier steps imply that the original list is nongraphic as well. \(\square\)

This explains why it is important to sort after each subtraction. The next reduction must remove a largest entry of the current list. Sorting does not change the entries or their graphicality; it ensures the procedure applies to the correct current sequence.

Worked Example: Even Sum, but Nongraphic

Test \((3,3,3,1,0)\). The list is already nonincreasing, all entries are nonnegative, and its largest entry \(3\) is at most \(n-1=4\). The degree sum is \(3+3+3+1+0=10\), which is even. Thus the quick tests do not reject it.

Remove the first \(3\) and subtract \(1\) from the next three entries, which are \(3,3,1\). These become \(2,2,0\); the remaining entry is \(0\). The reduced sequence is \((2,2,0,0)\). Now remove \(2\) and subtract \(1\) from the next two entries \(2,0\). They become \(1,-1\), leaving the other \(0\), so the reduced sequence is \((1,0,0,-1)\) after sorting.

The negative entry makes this reduced sequence nongraphic. By the Havel–Hakimi theorem, the original sequence is nongraphic too.

Check: The original sum is \(3+3+3+1+0=10\), even, and the largest entry \(3\) is within the bound \(4\). The rejection comes from the negative entry \(-1\) in the second reduction, not from either quick test.

Following a Failure Through Several Reductions

A sequence need not fail at its first reduction. Continue carefully, recording each sorted list, until a decisive condition appears. Every reduction before the failure is valid, and the equivalence in the Havel–Hakimi theorem carries the conclusion back to the original list.

Worked Example: A Nongraphic Sequence with a Later Failure

Consider \((4,4,4,1,1,1,1)\). It has \(n=7\), largest entry \(4\le6\), and sum \(4+4+4+1+1+1+1=16\), which is even. So neither the degree bound nor the parity test rejects it.

First reduction: Remove \(4\). The remaining entries are \(4,4,1,1,1,1\). Subtract \(1\) from the next four entries \(4,4,1,1\), obtaining \(3,3,0,0\); the two untouched entries are \(1,1\). After sorting, the result is \((3,3,1,1,0,0)\).

Second reduction: Remove \(3\). Subtract \(1\) from the next three entries \(3,1,1\), obtaining \(2,0,0\); the two remaining entries are \(0,0\). The sorted result is \((2,0,0,0,0)\).

Third reduction: Remove \(2\). The next two entries are both \(0\), so subtracting \(1\) from each gives \(-1,-1\). The result contains negative entries, hence is nongraphic. The equivalence at each previous reduction implies that \((4,4,4,1,1,1,1)\) is nongraphic.

Check: The first reduced list has sum \(3+3+1+1+0+0=8\); the second has sum \(2+0+0+0+0=2\). Each reduction removes a largest entry \(r\) and lowers the remaining sum by \(2r\), as expected: \(16-2(4)=8\), then \(8-2(3)=2\). The final failure is the required subtraction from two zero entries.

A Successful Process as a Contrast

A reduction that never produces a negative entry is not a failure certificate. If the process reaches all zeros, repeated use of the Havel–Hakimi equivalence shows that the original sequence is graphical. The next example includes a direct realization as an independent check of the result.

Worked Example: A Candidate That Reduces to Zeros

Test \((3,3,2,2,2,2)\). Its sum is \(3+3+2+2+2+2=14\), and its largest entry \(3\) is at most \(5\). Remove the first \(3\) and subtract \(1\) from the next three entries \(3,2,2\). The result is \((2,2,2,1,1)\).

Remove \(2\) and subtract \(1\) from the next two entries \(2,2\), giving \((1,1,1,1)\). Remove \(1\) and subtract \(1\) from the next entry \(1\), giving \((1,1,0)\). Remove \(1\) and subtract \(1\) from the next entry \(1\), giving \((0,0)\). The list consists of zeros, so the sequence is graphical by repeated application of the Havel–Hakimi theorem.

For a direct check, take \(V=\{1,2,3,4,5,6\}\) and \(E=\{12,23,34,45,56,61,14\}\). Vertices \(1\) and \(4\) each have degree \(3\); vertices \(2,3,5,6\) each have degree \(2\). Thus this graph realizes the original sequence.

Check: The graph has \(7\) edges, so the sum of its degrees is \(2|E|=2\cdot7=14\), matching \(3+3+2+2+2+2=14\).

How to Report Nongraphicality

A useful diagnosis identifies the first condition that fails, rather than merely stating that a list is impossible. For an immediate rejection, name the negative entry or compare the largest entry with \(n-1\). For a parity rejection, calculate the sum. For a Havel–Hakimi rejection, show the sorted lists and the exact subtraction that produces a negative entry (or identify a largest entry that is too large for the remaining list).

Keep the logical direction of each test in view. The basic bounds and even-sum condition are necessary, so failing one proves nongraphicality, but passing them alone proves nothing. Havel–Hakimi provides the stronger step-by-step test: each valid reduction preserves graphicality in both directions. In particular, do not call an intermediate list nongraphic just because it looks unusual; demonstrate the failed condition or continue the reductions.

A common mistake is to treat an even degree sum as a complete test. For \((3,3,3,1,0)\), the calculation \(3+3+3+1+0=10\) confirms even parity, but the two reductions above produce a negative entry. The correction is to use parity only as a quick necessary check, then continue with Havel–Hakimi when the sequence passes the quick tests.

Check Your Understanding

For each candidate, identify which test applies and show enough work to justify your conclusion.

Why is \((5,2,2,1)\) nongraphic, even though its entries sum to an even number?
Apply the parity test to \((3,3,2,2,1)\). Does that test decide graphicality?
Carry out Havel–Hakimi reductions on \((3,3,3,1,0)\) and identify the first negative entry.
Explain why a list of zeros at the end of a Havel–Hakimi process certifies graphicality.
Give one reason why passing the nonnegativity, maximum-degree, and even-sum checks does not by itself prove that a sequence is graphical.