Is the sequence (3, 3, 3, 1) graphical? Apply the Erdős-Gallai theorem.
AYes — the sum is 10, which is even, and even-sum sequences are always graphical
BNo — the prefix inequality fails at k = 2
CYes — the prefix inequality holds at k = 1, so no further checking is needed
DNo — the sequence must be strictly decreasing to be graphical
The sum is 10 (even) ✓. Check k=2: left side = 3+3 = 6. Right side = k(k−1) + Σmin(dᵢ,k) = 2(1) + min(3,2) + min(1,2) = 2 + 2 + 1 = 5. Since 6 > 5, the inequality fails at k=2, so the sequence is NOT graphical. Option A shows the key misconception: even sum is necessary but not sufficient. The prefix inequalities must also hold.
Question 2 Multiple Choice
In the Erdős-Gallai inequality, the right side includes Σᵢ₌ₖ₊₁ⁿ min(dᵢ, k) rather than just Σdᵢ. Why is the min(dᵢ, k) cap necessary?
ABecause outside vertices can only connect to each other, not to the top-k group
BBecause each outside vertex can contribute at most k edges to the top-k group, since the group has only k members
CBecause min(dᵢ, k) ensures outside vertices have lower degree than top-k vertices
DBecause dᵢ alone would double-count edges within the outside group
Each vertex outside the top-k group can connect to at most k members of the group — the group only has k members. Even if an outside vertex has degree dᵢ > k, at most k of those edges go to the group. So min(dᵢ, k) correctly caps each outside vertex's maximum contribution to the top-k group's total degree. This makes the right side a genuine upper bound on what the top-k vertices can collectively achieve.
Question 3 True / False
A sequence of non-negative integers with an even sum is typically 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 fails the Erdős-Gallai prefix inequality at k=2 and cannot be realized as a simple graph's degree sequence. The theorem requires both the even-sum condition and the prefix inequalities at every k. Many even-sum sequences are non-graphical.
Question 4 True / False
To apply the Erdős-Gallai theorem, it is sufficient to check the prefix inequality mainly at k = 1 and k = n.
TTrue
FFalse
Answer: False
The prefix inequality must hold for every k from 1 to n. Failure at any single k is enough to disqualify the sequence. While in practice many sequences fail (or pass) early — at small values of k — there is no guarantee that checking only the endpoints is sufficient. The complete check requires verifying all n inequalities.
Question 5 Short Answer
Explain the intuition behind the Erdős-Gallai prefix inequality: why does k(k−1) + Σ min(dᵢ, k) represent a bound on what the top-k vertices can achieve?
Think about your answer, then reveal below.
Model answer: The right side counts the maximum possible edges the k highest-degree vertices could collectively have in any simple graph. The term k(k−1) is the number of edges in a complete graph on k vertices — the most those k vertices can share among themselves. The term Σ min(dᵢ, k) adds the maximum contribution from each remaining vertex: each outside vertex can supply at most k edges to the group. If the actual degree sum of the top-k vertices exceeds this bound, no valid simple graph can exist.
This is a packing argument: can the high-degree vertices actually be satisfied given the edges available to them? The bound is tight because it counts every possible edge the top-k vertices could have — edges within the group and edges from outside. If the sequence demands more edges than this maximum allows, the degree requirements are geometrically impossible. The theorem is both necessary and sufficient: it fails precisely when no graph can accommodate the requirements.