Question

1) a) Let k ≥  2 and let G be a k-regular bipartite graph. Prove that G has no cut-edge. (Hint: Use the bipartite version of handshaking.)

b) Construct a simple, connected, nonbipartite 3-regular graph with a cut-edge. (This shows that the condition “bipartite” really is necessary in (a).)

2) Let F_n be a fan graph and Let a_n = τ(F_n) where τ(F_n) is the number of spanning trees in F_n. Use deletion/contraction to prove that a_n = 3a_n-1 - a_n-2 for n ≥  3. See if you can recognize the sequence a_1, a_2, a_3, a_4 . . .

3) Let L_n be the graph obtained from K_n by deleting one edge. Determine τ(L_n). (Hint: Use Cayley’s formula as a starting point.)

4) Let K_p,q denote the complete bipartite graph with partite sets of sizes p and q. Use the Matrix-Tree Theorem to calculate τ(K_p,q). Hint: Find an explicit basis for ℝ^(p+q) consisting of eigenvectors of the Laplacian matrix L(K_p,q).

5) Let G = (V, E) be a connected graph, let T, T' be spanning tress of G, and let e ∈ T\T'. Prove that there exists an edge e' ∈  T'\T such that both T-e+e' and T'+e+e' are spanning trees. (This is known as the “symmetric exchange law.”)

6) Let G be a connected graph with weight function w : E(G) → ℝ_(>0)

a) Suppose that C ⊆ G is a cycle and e ∈ C is an edge of maximum weight (i.e., w(e) ≥ w(e') for all e' ∈ C). Prove that G has an MST (Minimum Spanning Tree) not containing e.

b) Use (a) to show that the following algorithm produces an MST for all G and w:

Let T := G

while T contains a cycle do:

Let C be a cycle

Let e be an edge of C of maximum weight

Set T := T - e

Return T

Answer 1