A student claims there exists a simple graph with 4 vertices whose degree sequence is (3, 3, 1, 1). The sum is 8, which is even — so shouldn't it be realizable? Is the student correct?
AYes, an even sum guarantees the sequence is graphical
BNo, the Erdős–Gallai condition fails: the two degree-3 vertices must each connect to all three other vertices, forcing the degree-1 vertices to actually have degree 2
CNo, because a simple graph with 4 vertices cannot have any vertex of degree 3
DYes, the Hakimi algorithm would successfully construct such a graph
Even sum is necessary but not sufficient. In a 4-vertex graph, a vertex of degree 3 must connect to all three other vertices. If both high-degree vertices need degree 3, vertex A connects to B, C, D, and vertex B connects to A, C, D. This gives C and D degree 2 each — but the sequence claims they have degree 1. Contradiction: no such simple graph can exist. The Erdős–Gallai condition catches exactly this: for k=2, the sum of the top two degrees (6) exceeds what the remaining vertices can absorb (max 4).
Question 2 Multiple Choice
A student finds the sequence (2, 2, 1, 1, 1, 1) and notices its sum is even (8). They conclude that an even sum is both necessary and sufficient for a sequence to be graphical. What is wrong with this reasoning?
ANothing — an even sum is both necessary and sufficient for graphical sequences
BAn even sum is necessary but not sufficient; Erdős–Gallai conditions impose additional constraints that some even-sum sequences fail
CThe sum must be divisible by 4, not just even
DSequences with odd-degree vertices can never be graphical, regardless of the sum
The handshaking lemma tells us the sum of degrees must be even — a necessary condition. But it is not sufficient. For example, (3, 3, 1, 1) has even sum 8 yet is not graphical. The Erdős–Gallai theorem provides a complete characterization: a sequence is graphical if and only if it satisfies both the even-sum condition and the Erdős–Gallai inequalities for every k. The student's reasoning confuses a necessary condition with a necessary-and-sufficient one.
Question 3 True / False
If the sum of a degree sequence is odd, no simple graph with that degree sequence can exist.
TTrue
FFalse
Answer: True
This follows directly from the handshaking lemma: the sum of all vertex degrees equals exactly twice the number of edges (each edge contributes 1 to each of its two endpoints' degrees). Therefore the degree sum is always even. An odd-sum sequence violates this, so no simple graph — or any graph without self-loops — can realize it. This is the quickest test for ruling out a sequence: check parity first.
Question 4 True / False
Two graphs with the same degree sequence should be isomorphic — they have the same structure.
TTrue
FFalse
Answer: False
Many non-isomorphic graphs share the same degree sequence. For example, both the path P₄ and the star K₁,₃ have three vertices of degree 1 in related configurations, and there exist pairs of 6-vertex non-isomorphic graphs with degree sequence (2,2,2,2,2,2) — one being a 6-cycle, the other being two disjoint triangles. The degree sequence is a coarse summary of graph structure; it tells you the 'shape' of connectivity in aggregate but not which specific vertices are connected.
Question 5 Short Answer
State the handshaking lemma and explain why it is true from first principles.
Think about your answer, then reveal below.
Model answer: The handshaking lemma states that the sum of all vertex degrees equals twice the number of edges. It is true because each edge {u, v} contributes exactly 1 to the degree of u and exactly 1 to the degree of v — a total of 2 per edge. Summing degrees across all vertices is equivalent to counting each edge twice. Therefore: sum of degrees = 2 × |E|.
The immediate consequence is that degree sums are always even, and that an odd number of odd-degree vertices is impossible (since the sum of an odd count of odd numbers is odd, which can't equal 2|E|). These simple facts constrain degree sequences and are the first checks to apply before using more powerful tools like Erdős–Gallai.