Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
What have you tried? –  Qiaochu Yuan May 1 '12 at 18:08
    
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

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.