# Find the number of spanning trees of a graph

Let $$n=2k+1$$, where $$k ∈ℕ$$. Let there be two non-intersecting paths $$a_1,a_2,...,a_n$$ and $$b_1,b_2,...,b_n$$. Let us also add edges $$a_1b_1$$, $$a_{k+1}b_{k+1}$$ and $$a_nb_n$$. Find the number of different spanning trees of such graph.

If we didn't add the edge $$a_{k+1}b_{k+1}$$, then the number of spanning trees would be simply $$2n$$. How do I find the number of spanning trees with that edge added? I'm not quite sure how to exclude the graphs that don't include all the vertices (i.e that are not spanning trees).

• I am not sure about understanding your problem, can you please explain what is exactly your graph? – Youem May 13 at 18:58

So we have to count all the ways to delete two edges such that remaining graph is connected. If we remove $$a_{k + 1} b_{k + 1}$$, then we can also remove any other edge. This gives us $$2n$$ spanning trees.

So now assume that we do not remove $$a_{k + 1} b_{k + 1}$$. Instead we have to remove two other edges. Notice that if we remove one edge to the left of $$a_{k + 1}b_{k + 1}$$ and one edge to the right, our graph will still be connected. Otherwise it will be disconnected. This gives us $$n \cdot n$$ spanning trees.

In total we have $$2n + n^2$$.

A spanning tree as $$2n-1$$ edges, so you need to remove $$2$$ edges.

• Check that removing any two of the three added edges will yield a spanning tree. (How many ways you can do this?)

• At least one of the three added edges must be removed, so the remaining cases are removing one of the three added edges along with one of the edges in the two original paths.

• If you remove $$a_{k+1} b_{k+1}$$, you may then remove any one of the edges in the original two paths to obtain a spanning tree. (How many ways can you do this?)
• If you remove $$a_1 b_1$$ or $$a_n b_n$$, there still is another cycle in the graph, so you need to then choose an edge that is not only one of the ones in the original two paths, but also in this cycle. (How many ways can you do this?)