1) a) Let k ?  2 and let G be a k-regular bipartitegraph. Prove that G has no cut-edge. (Hint: Use the bipartiteversion of handshaking.)

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

2) Let F_n be a fan graph and Let a_n = ?(F_n) where ?(F_n) isthe number of spanning trees in F_n. Use deletion/contraction toprove that a_n = 3a_n-1 - a_n-2 for n ?  3. See if youcan 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 startingpoint.)

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

5) Let G = (V, E) be a connected graph, let T, T' be spanningtress of G, and let e ? TT'. Prove that there exists an edge e'?  T'T such that both T-e+e' and T'+e+e' are spanningtrees. (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 maximumweight (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 MSTfor 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