Project ForgeAn ordered n-tuple (d₁,d₂,...,dₙ) with d₁ ≥ d₂ ≥ ... ≥ dₙ is called graphic if there exists a simple undirected graph with n vertices having degrees d₁,d₂,...,dₙ respectively. Which of the following 6-tuples is NOT graphic?
- A(1, 1, 1, 1, 1, 1)
- B(2, 2, 2, 2, 2, 2)
- (3, 3, 3, 1, 0, 0)
- D(3, 2, 1, 1, 1, 0)
Explanation
The two 0-degree vertices in (3,3,3,1,0,0) are isolated and irrelevant, so this reduces to checking whether (3,3,3,1) is graphic on 4 vertices. By the Erdős–Gallai theorem, for k=2: d₁+d₂ ≤ k(k−1) + Σᵢ₌₃ⁿ min(dᵢ,k), i.e. 3+3=6 must be ≤ 2(1) + min(3,2)+min(1,2) = 2+2+1 = 5. Since 6 > 5, the inequality fails, so (3,3,3,1) — and hence (3,3,3,1,0,0) — is NOT graphic. (The other three options are all straightforward to realize: a perfect matching for (1,1,1,1,1,1), a 6-cycle for (2,2,2,2,2,2), and a small explicit construction for (3,2,1,1,1,0).)
Source: GATE CS 2014 (Session 1) (2014)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.