0
$\begingroup$

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!

  • 0
    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 edge2012-05-01

1 Answers 1

1

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$.

  • 0
    No worries, thank you so much for your assistance2012-05-01