Introduction to Graph Theory · Problem 5.6

Trees and arborescences — Darij Grinberg

Mathematics — Graph Theory · spanning-trees-counting

Problem

Fix

m \geq 1

. Let

G

be the simple graph with

3m + 2

vertices

a, b, x_1, x_2, \ldots, x_m, y_1, y_2, \ldots, y_m, z_1, z_2, \ldots, z_m

and the following

3m + 3

edges:

ax_1, \; ay_1, \; az_1,

x_i x_{i+1}, \; y_i y_{i+1}, \; z_i z_{i+1} \quad \text{for all } i \in \{1, 2, \ldots, m-1\},

x_m b, \; y_m b, \; z_m b.

(Thus, the graph consists of two vertices

a

and

b

connected by three paths, each of length

m+1

, with no overlaps between the paths except for their starting and ending points.) Compute the number of spanning trees of

G

. [To argue why your number is correct, a sketch of the argument in 1--2 sentences should be enough; a fully rigorous proof is not required.]