nongraphical

Nongraphical is an adjective used in graph theory to describe a degree sequence that cannot be realized as the degree sequence of any simple graph. In other words, a sequence is nongraphical if no simple graph exists whose vertices have degrees matching the sequence. By contrast, a graphic sequence can be realized.

Determining whether a sequence is graphic relies on established criteria and algorithms. A basic prerequisite is that the sum of the degrees must be even, since it equals twice the number of edges in any graph. The Erdős–Gallai theorem provides a necessary and sufficient set of inequalities for a nonincreasing sequence d1 ≥ d2 ≥ ... ≥ dn to be graphic. The Havel–Hakimi algorithm offers a constructive procedure: repeatedly reduce the largest degree and adjust the remaining degrees; if the process yields a contradiction, the original sequence is nongraphical.

Examples help illustrate nongraphicality. Any sequence with an odd sum is nongraphical, because degree sums in graphs are always even. For instance, the sequence (2, 2, 2, 1) sums to 7, which is odd, so it cannot be realized as a simple graph’s degree sequence. More complex nongraphical sequences can fail the Erdős–Gallai inequalities even when their sum is even.

The concept of nongraphical sequences is central to the graph realization problem, which asks whether a given degree sequence can be realized as a simple graph and, if so, how. Understanding nongraphical sequences helps delineate the boundary between abstract degree lists and actual graph structures.

See also: graphic sequence, Erdős–Gallai theorem, Havel–Hakimi algorithm, graph realization problem.