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
    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.2012-05-01
  • 0
    @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?2012-05-01
  • 0
    did you mean, you can remove any of the other x + y - 1 edges to get a spanning tree?2012-05-01
  • 0
    case 1: ((x + y) choose (x + y - 1)) ?2012-05-01
  • 0
    case 2: ((x + y - 1) choose (x + y - 2)) ?2012-05-01
  • 0
    There aren't $x+y-1$ other edges; there are only $x+y-2$ other edges. ($G$ has only $x+y-1$ edges altogether.) And no binomial coefficients are needed in either case.2012-05-01
  • 0
    true, i apologize. I still can't gather a final formula / answer2012-05-01
  • 0
    @John: Hold on a bit, and I'll expand my answer.2012-05-01
  • 0
    that helps a lot and i think I am at a general formula, but i have one question regarding what you added to your hint/answer. Should it be 4 * 5 instead of 4 * 6 since we have 4 of 5 edges to choose from c5 and 5 of 6 edges to choose from c6?2012-05-01
  • 0
    @John: Yep: computational slip-up on my part, which I've now fixed.2012-05-01
  • 0
    No worries, thank you so much for your assistance2012-05-01