Guichard-Combinatorics-Graph-Theory · Problem 5.1.9

Graph Theory

Mathematics — Probability · graph-theory-basics

Problem

Show that the condition on the degrees in theorem 5.1.3 is equivalent to this condition:

\sum_{i=1}^n d_i

is even and for all

k \in \{1, 2, \ldots, n\}

, and all

\{i_1, i_2, \ldots, i_k\} \subseteq [n]

\sum_{j=1}^k d_{i_j} \leq k(k-1) + \sum_{i \notin \{i_1, i_2, \ldots, i_k\}} \min(d_i, k).

Do not use theorem 5.1.3.