Degree sequence: sorted vertex degrees d₁≥d₂≥...≥dₙ. A sequence is graphical if realizable as a simple graph. Erdős-Gallai (1960): graphical iff Σᵢ₌₁ᵏ dᵢ ≤ k(k-1)+Σᵢ₌ₖ₊₁ⁿ min(dᵢ,k) for all k, and Σdᵢ is even.
How to Use
Enter degrees:
- Sort: Non-increasing order
- Check: Graphical?
- Sum: Must be even
Erdős-Gallai
A non-increasing sequence d₁,...,dₙ is graphical iff: (1) Sum is even. (2) For each k=1..n: Σᵢ₌₁ᵏ dᵢ ≤ k(k-1)+Σᵢ₌ₖ₊₁ⁿ min(dᵢ,k). This elegant characterization is both necessary and sufficient.
Hakimi Algorithm
Constructive proof: remove largest degree d₁, subtract 1 from the next d₁ largest degrees, repeat. If you reach all zeros, the sequence is graphical. This gives an actual graph realization.
Step-by-Step Instructions
- 1Enter degrees.
- 2Sort sequence.
- 3Check even sum.
- 4Apply Erdős-Gallai.
- 5Try Hakimi.