Guichard-Combinatorics-Graph-Theory · Problem 5.1.3

Graph Theory

Mathematics — Probability · graph-theory-basics

Problem

Suppose

d_1 \geq d_2 \geq \cdots \geq d_n

and

\sum_{i=1}^n d_i

is even. Prove that there is a multigraph (no loops) with degree sequence

d_1, d_2, \ldots, d_n

if and only if

d_1 \leq \sum_{i=2}^n d_i