Even sum is necessary but not sufficient. Each of the three degree-3 vertices needs 3 neighbors, but in a 4-vertex graph, each vertex can have at most 3 neighbors total. The degree-1 vertex can serve as a neighbor only once, and the three degree-3 vertices would need to share connections in a way that is impossible without multi-edges or self-loops. The Erdős–Gallai inequalities catch exactly this kind of overcommitment of degree budget.
Question 2 Multiple Choice
The Erdős–Gallai theorem checks that for each k, the sum of the top-k degrees is at most k(k−1) plus the sum of min(dᵢ, k) for the remaining vertices. What does this inequality fundamentally constrain?
AThe total number of edges in the graph, ensuring it does not exceed the maximum for n vertices
BHow many edges the k highest-degree vertices can collectively have, accounting for edges among themselves and edges to the remaining vertices
CWhether the graph contains a subgraph with a Hamiltonian cycle
DThe chromatic number of any graph realizing the sequence
The right side of the inequality has two parts: k(k−1) counts the maximum possible edges among the top-k vertices themselves (a complete graph on k vertices has k(k−1)/2 edges, contributing degree k−1 to each of the k vertices), and the sum of min(dᵢ, k) counts how many connections the remaining n−k vertices can contribute to the top-k group. If the top-k vertices claim more total degree than these two pools can supply, the sequence is impossible — no matter how you try to draw it.
Question 3 True / False
By the handshaking lemma, the sum of all vertex degrees in any simple graph must be even.
TTrue
FFalse
Answer: True
Every edge contributes exactly 2 to the total degree count — one for each of its two endpoints. Therefore the sum of all degrees equals 2|E|, which is always even. This is the first and simplest necessary condition for a sequence to be graphical. A sequence with odd sum — like (3, 3, 1) — can be rejected immediately without further analysis.
Question 4 True / False
A non-increasing sequence of non-negative integers with an even sum is generally graphical — it can typically be realized as the degree sequence of some simple graph.
TTrue
FFalse
Answer: False
Even sum is necessary but not sufficient. The sequence (3, 3, 3, 1) has even sum 10 but is not graphical: the three degree-3 vertices cannot all find 3 distinct neighbors in a 4-vertex simple graph. The Erdős–Gallai theorem exists precisely because even sum alone fails to capture all the constraints. Additional inequalities are required to ensure the degree budget of the highest-degree vertices can actually be distributed as valid edges.
Question 5 Short Answer
Why does the Erdős–Gallai theorem need to check a family of prefix inequalities rather than just verify that the total sum is even? What structural impossibility does each inequality detect?
Think about your answer, then reveal below.
Model answer: Even sum guarantees that the total degree budget could in principle correspond to some number of edges, but it does not guarantee that the degrees can be distributed among specific vertices without conflict. Each Erdős–Gallai inequality checks whether the k highest-degree vertices can collectively be satisfied given (a) the edges they can share among themselves and (b) the connections the remaining vertices can provide. If any prefix violates the inequality, those k vertices are overclaiming degree that cannot be physically supplied — an impossibility no matter how the rest of the graph is arranged.
The handshaking lemma is a global constraint; the Erdős–Gallai inequalities are local constraints on every subset of the highest-degree vertices. A globally valid sum can still fail locally — a few high-degree vertices can demand more connections than their neighborhood can supply. The Havel-Hakimi algorithm makes this concrete: if you greedily connect the highest-degree vertex to its required neighbors and the process fails, you have found the impossibility that Erdős–Gallai's inequality detected algebraically.