Guichard-Combinatorics-Graph-Theory · Problem 5.1.13

Graph Theory

Mathematics — Probability · graph-theory-basics

Problem

Prove the ``if'' part of theorem 5.1.3, as follows: The proof is by induction on

s = \sum_{i=1}^n d_i

. This is easy to see if

s = 2

, so suppose

s > 2

. Without loss of generality we may suppose that

d_n > 0

. Let

t

be the least integer such that

d_t > d_{t+1}

, or

t = n - 1

if there is no such integer. Let

d'_t = d_t - 1

d'_n = d_n - 1

, and

d'_i = d_i

for all other

i

. Note that

d'_1 \geq d'_2 \geq \cdots d'_n

. We want to show that the sequence

\{d'_i\}

satisfies the condition of the theorem, that is, that for all

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

\sum_{i=1}^k d'_i \leq k(k-1) + \sum_{i=k+1}^n \min(d'_i, k).

There are five cases: •

k \geq t

•

k < t

d_k < k

•

k < t

d_k = k

•

k < t

d_n > k

•

k < t

d_k > k

d_n \leq k

By the induction hypothesis, there is a simple graph with degree sequence

\{d'_i\}

. Finally, show that there is a graph with degree sequence

\{d_i\}