Introduction to Graph Theory · Problem 2.10

Simple graphs — Darij Grinberg

Mathematics — Graph Theory · kneser-graph-connectedness

Problem

Let

k \in \mathbb{N}

. Let

S

be a finite set. Recall that the Kneser graph

K_{S,k}

is the simple graph whose vertices are the

k

-element subsets of

S

, and whose edges are the unordered pairs

\{A, B\}

consisting of two such subsets

A

and

B

that satisfy

A \cap B = \varnothing

. Prove that this Kneser graph

K_{S,k}

is connected if

|S| \geq 2k + 1

. [Remark: Can the ``if'' here be replaced by an ``if and only if''? Not quite, because the graph

K_{S,k}

is also connected if

|S| = 2

and

k = 1

(in which case it has two vertices and one edge), or if

|S| = k

(in which case it has only one vertex), or if

k = 0

(in which case it has only one vertex). But these are the only ``exceptions''.]