Combinatorics and Graph Theory · Problem 5.7.3

Graph Theory — David Guichard

Mathematics — Combinatorics · connectivity

Problem

Suppose

G

is simple with degree sequence

d_1 \leq d_2 \leq \cdots \leq d_n

, and for

k \leq n - d_n - 1

d_k \geq k

. Show

G

is connected.