Grinberg-Introduction-Graph-Theory · Problem 5.9

Trees and arborescences

Mathematics — Graph Theory · spanning-trees-graph-connectivity

Problem

Let

G

be a connected multigraph. Let

\mathcal{S}

be the simple graph whose vertices are the spanning trees of

G

, and whose edges are defined as follows: Two spanning trees

T_1

and

T_2

G

are adjacent (as vertices of

\mathcal{S}

) if and only if

T_2

can be obtained from

T_1

by removing an edge and adding another (i.e., if and only if there exist an edge

e_1

T_1

and an edge

e_2

T_2

such that

e_2 \neq e_1

and

T_2 \setminus e_2 = T_1 \setminus e_1

). Prove that the simple graph

\mathcal{S}

is itself connected. (In simpler language: Prove that any spanning tree of

G

can be transformed into any other spanning tree of

G

by a sequence of legal ``remove an edge and add another'' operations, where such an operation is called legal if its result is a spanning tree of

G