Finding the number of spanning tree of a particular graph

Question

I have the following graph: start with a graph $C_n$(a n-cycle), where $n$ is at least 4, and we label the vertices from $1$ to $n$. Now, let an extra vertex $x$ be connected to the vertex with label 1 in $C_n$, and also connected to the vertex with label $m$ in $C_n$, and denote this graph as $G_{n,m}$, and find a closed formula of spanning trees in $G_{n,m}$, in terms of $n,m$. Here are an example of what this graph looks like:

For $G_{4,3}:$

For $G_{6,4}:$

Immediately I think about edge contraction recurrence, $\tau(G)=\tau(G-e)+\tau(G*e)$. Take $G_{6,4}$ as example: suppose the edge between $x$ and vertex labelled 1 is $e_1$ and the edge between $x$ and vertex labelled 4 is $e_2$. Apply edge contraction recurrence to $e_2$, we get $\tau(G_{6,4})=\tau(G_{6,4}-e)+\tau(G_{6,4}*e)$. Apply the edge contraction recurrence to $e_1$on $\tau(G_{6,4}-e)$, it becomes $\tau(C_n)$-- so thats is $n$. But the tricky part is $\tau(G_{6,4}*e)$. A picture of $G_{6,4}*e$ is provided:

Now contract the edge between vertex $1$ and $4,x$ and use edge contraction recurrence, we get a graph that is $C_n$ so that gives $n$ spanning subtrees, summing it with a graph that looks like this:

and I'm really not sure how many spanning subtree this graph has. After doing some small examples, I think for the specific case here there is $2*3$ spanning subtrees, but how can I generalize this to a general $m,n$? Thank you in advance!

Answer 1

Another useful property of $\tau(G)$, the number of spanning trees of $G$, is the following.

Suppose $G$ consists of two subgraphs $G_1, G_2$ which have only one vertex, $v$, in common. All edges of $G$ are either edges of $G_1$ or edges of $G_2$. Then to pick a spanning tree of $G$, we must pick a spanning tree of $G_1$ and a spanning tree of $G_2$ - and whichever way you combine those works. This tells us that $$\tau(G) = \tau(G_1) \cdot \tau(G_2).$$

In your case, when you contract both edges out of $x$, you get exactly this structure: the graph you get has two cycles that meet at one vertex. The rule above should help you deal with this graph. When you delete one edge out of $x$ and contract the other, whichever way you do it, you get $C_n$, and you can find $\tau(C_n)$. Finally, you get no spanning trees if you delete both edges out of $x$, because then the graph is disconnected.

Answer 2

HINT: $G_{n,m}$ has three cycles: the original $C_n$, a $C_{n-m+3}$, and a $C_{m+1}$. In order to get a spanning tree, you must remove enough edges to break each of these cycles without disconnecting the graph. You have $n+1$ vertices and $n+2$ edges, while a tree with $n+1$ vertices must have $n$ edges, so you have to remove exactly $2$ edges.

• If you remove one of the two new edges incident at $x$, you can remove any of the $n$ original edges to get a spanning tree. How many spanning trees can you get in this way?
• The only other possibility is to remove one old edge from each of the shorter cycles. How many old edges are there in the $C_{n-m+3}$ cycle, and how many are there in the $C_{m+1}$ cycle? How many spanning trees altogether can you get in this way?