Spanning Tree Workshop

Math 428 (Weibel) October 1, 1997

If G is a connected (p, q)-graph, its genus is the number g = q − p + 1. Let T be a spanning tree in G.

1. (Showing that the genus is a lower bound for the number of cycles in G.)

(a) Show that there are exactly g edges not in T.

(b) If e is an edge not in T, joining vertices u and v, and P is the path in T from u to v, show that P + {e} is a cycle in G.

(c) Parts (a) and (b) show that G has at least g cycles. What is the smallest genus g such that there can be more than g cycles? Illustrate with an example.

Now let X denote the set of edges in G which are not in T. By part 1(a), X has g elements.

2. If C is a cycle in G, set S(C) = X ∩ C. That is, S(C) denotes the set of edges in C which are not in T.

(a) Show that S(C) ≠ ∅.

(b) If C′ ≠ C, show that S(C′) ≠ S(C).

(c) Deduce that there are at most 2^{g} − 1 cycles in G.

(d) Show by example that not every subset S ≠ ∅ of X comes from a cycle in G. Note that if S = {e} then C is described by 1(b).