# Graph Theory - Spanning Trees

Consider a graph $G$ composed of two cycles which share an edge. $C_x$ is the cycle of length $x$ and $C_y$ is the cycle length $y$, for $x,y \ge 3$. (for example, if $x = 6$ and $y = 5$, then $C_x$ has $6$ edges and $C_y$ has $5$ edges, but the graph $G$ (composed of $C_x$ and $C_y$ sharing an edge) contains $9$ edges, basically a pentagon and a hexagon together sharing a side).

What is a formula for the number of spanning trees of $G$? It is possible to draw out all the different possibilities of $x,y \ge 3$, but very tedious - so I am looking for the formula to plug in the cycle sizes and getting back the number of spanning trees.

Thanks!

• I have broken the graph up into two parts, just as @Brian has done below. 1. Spanning trees of G that do not contain the shared edge and 2. Spanning trees of G that do contain the shared edge – John May 1 '12 at 18:44

HINT: Break the count into two cases:

1. spanning trees that do not contain the common edge;
2. spanning trees that do contain the common edge.

In Case 1 you can remove any one of the remaining edges to get a spanning tree. In Case 2 you must remove one non-common edge from each cycle.

Added: Let's look at your example with $C_5$ and $C_6$. $G$ has $5+6-2=9$ vertices, so a spanning tree must have $8$ edges. $G$ has $5+6-1=10$ edges, so you'll have to remove two edges. It can't be just any two edges, however: if you remove two of the edges that belong to $C_5$ but not to $C_6$, for instance, you won't get a tree.

Suppose (Case 1) that you remove the common edge. What's left is a cycle of length $9$, and you can remove any of those $9$ edges to leave a spanning tree. Thus, Case 1 gives you $9$ spanning trees.

Now suppose that you don't remove the common edge. Then you must remove one of the $4$ edges that belong only to $C_5$, so as to break the $C_5$ cycle, and you must remove one of the $5$ edges that belong only to $C_6$, so as to break the $C_6$ cycle as well. It doesn't matter which of the $4$ non-common edges of $C_5$ you pick, and it doesn't matter which of the non-common edges of $C_6$ you pick: removing any pair containing one of each will leave you with a spanning tree of $G$. There are $4\cdot5=20$ such pairs, so Case 2 gives you another $20$ spanning trees, for a total of $9+20=29$ spanning trees.

Now just go through the same argument in general, replacing $5$ by $x$ and $6$ by $y$, to get a general formula in terms of $x$ and $y$ for the number of spanning trees of $G$.

• I have gone through drawing out all possibilities for some of the smaller cases, looking for a pattern. It may be and inclusion exclusion of choosing n edges from x.. but I can't come up with a formula. – John May 1 '12 at 18:27
• @John: You're working much too hard. $G$ has $1$ common edge, $x-1$ other edges in $C_x$, and $y-1$ other edges in $C_y$. You must remove $2$ of these edges to get a spanning tree. If you remove the common edge, you can remove any of the other $x+y-2$ edges to get a spanning tree. If you keep the common edge, you must remove one of the other $x-1$ edges of $C_x$ and one of the other $y-1$ edges of $C_y$; in how many ways can you do that? – Brian M. Scott May 1 '12 at 18:30
• did you mean, you can remove any of the other x + y - 1 edges to get a spanning tree? – John May 1 '12 at 18:39
• case 1: ((x + y) choose (x + y - 1)) ? – John May 1 '12 at 18:42
• case 2: ((x + y - 1) choose (x + y - 2)) ? – John May 1 '12 at 18:43