Does a valid degree sequence determine the graph?

Usually not; different graphs can share the same degree counts.

Why must the degree sum be even?

In a simple undirected graph, every edge is incident to two nodes and adds 1 to each endpoint's degree.

Does the standard test require the graph to be connected?

No. Ordinary graphicality asks for some simple undirected realization; connectivity is an additional requirement that must be addressed separately.

AI Glossary / Graphs and symbolic AI / Intermediate

Graphical degree sequence

Definition

A graphical degree sequence is a list of nonnegative integers that can be realized as the node degrees of a graph of the specified kind. In the standard simple, undirected setting, the question is whether a graph with no self-loops or parallel edges can have exactly those degrees. Passing the test establishes existence, not a unique network.

What it means

A degree counts how many edges meet a node in a simple undirected graph. A requested sequence such as 2, 2, 1, 1 asks for four nodes with those connection counts. Some lists are possible and others are internally inconsistent, even when each individual count appears reasonable.
The graph model is essential. Directed graphs distinguish incoming and outgoing degrees, while graphs permitting repeated edges or loops follow different conditions. State the model before applying a graphicality test. A result for simple undirected graphs should not be transferred automatically to another kind of network.

How it works

Some quick checks are necessary: degrees must be nonnegative integers, no degree can exceed n minus 1 for n nodes, and their sum must be even because each edge contributes two degree units. These checks alone are not sufficient.
Complete tests include the Erdős-Gallai criterion and the Havel-Hakimi procedure. Havel-Hakimi repeatedly sorts the remaining degrees, removes the largest value d, and subtracts 1 from the next d largest values. Reaching all zeros succeeds; an impossible subtraction or negative residual fails. NetworkX exposes both methods through its is_graphical function. Testing existence and constructing a particular realization are related but separate operations.

Three practical examples

A synthetic-network exercise checks requested connection counts before attempting to generate a sample graph.
A data-quality review detects an impossible degree summary produced by an incorrect aggregation step.
A graph-theory class compares several networks sharing a degree sequence to understand which structural information degree counts leave unspecified.

Think of it this way

Think of each node as requesting a number of handshakes at a gathering, with no person shaking their own hand and each pair shaking at most once. The list is graphical if all requests can be satisfied together. The analogy is limited because real network edges may be directed, weighted, repeated, or constrained by rules that ordinary degree graphicality does not consider.

Worked example

Compare two requested sequences on four nodes. First take 2, 2, 1, 1. A path A-B-C-D realizes it: nodes B and C have degree 2, while A and D have degree 1. The degree sum is 6, agreeing with twice the three edges.
Havel-Hakimi also confirms this. Remove 2 and subtract 1 from the next two entries of 2, 1, 1, producing 1, 0, 1. Sort to 1, 1, 0. Remove 1 and subtract from the next entry, leaving 0, 0. The process succeeds.
Now take 3, 3, 1, 1. Its sum is 8 and its largest value is the permitted maximum 3, so the quick checks pass. But removing the first 3 and reducing the other three entries gives 2, 0, 0. The remaining node requesting degree 2 would need connections to two nodes with no available degree. The sequence fails. Equivalently, the two degree-3 nodes must both connect to each degree-1 node, forcing those latter nodes to have degree at least 2: a contradiction.

Illustrative case study

In a fictional exercise, Pine Network Studio asks for four anonymous devices with degrees 3, 3, 1, 1. Its generator repeatedly fails, and the team initially suspects a random-seed problem. A graphicality check reveals that the request itself is impossible for a simple undirected network.
The team corrects the specification and distinguishes two questions in its interface: whether the degree sequence is feasible, and whether a generated graph satisfies additional requirements such as connectivity. This invented case illustrates validation before generation, without claiming measured performance or a real deployment.

Common misconceptions and mistakes

An even degree sum does not guarantee graphicality, as the worked example shows. Conversely, a graphical sequence does not identify one unique graph or determine communities, shortest paths, or connectivity in general.
Graphicality also does not guarantee that a permitted graph satisfies application-specific restrictions. A sequence might be realizable only by edges your project forbids, or admit realizations that fail an additional connectivity requirement. Sorting the list is useful for the mathematical test, but a construction for named nodes must preserve which requested degree belongs to which node.

Business use

The concept is useful wherever a project generates, validates, or studies networks from degree information. It provides an early feasibility check that can prevent debugging a construction process whose specification has no solution.
Record whether the network is directed, whether loops or repeated edges are allowed, and whether node identities carry extra constraints. Separate degree feasibility from the quality or realism of generated examples. Many networks can satisfy a degree specification while differing in business-relevant relationships. A successful test is a structural consistency result, not evidence that a synthetic network faithfully represents an organization or population.

Check your understanding

Why does 3, 3, 1, 1 fail even though the sum is even?

Answer: Both degree-3 nodes must connect to all other nodes. Each of the proposed degree-1 nodes would then receive two connections, contradicting its requested degree.

Related terms

Node degree
degree sequence
simple graph
Havel-Hakimi algorithm
Erdős-Gallai theorem
graph realization
connectivity
synthetic network

Learn next

Apply Havel-Hakimi by hand to several small lists and draw a realizing graph whenever the test succeeds. Then compare a six-cycle with two separate triangles: both have six degree-2 nodes, but one is connected and the other is not.

Sources

Sources: NetworkX, is_graphical documentation and cited graphicality algorithms: https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.graphical.is_graphical.html

Previous: Graphical data editing Next: Graphical lasso