How to derive the number of spanning tree in this graph

144 Views Asked by At

Given this undirected graph $G_n$graph

where $n>2$, Let $h_n$ be number of possible spanning tree ($h_1=0$) and let $g_n$ be the number of sides connecting node $1$ and node $n$. Then, how can I express $g_n$ using $h_n$ and $h_{n-1}$? Can someone tell me how to derive this?

1

There are 1 best solutions below

0
On BEST ANSWER

You can use the well-known (and easily derived) formula $t(G)=t(G-e)+t(G/e)$ (*), where $t(G)$ denotes the number of spanning trees of (multi)graph $G$ and $G/e$ denotes the contraction (delete $e$ and identify its endpoints). Note that this contraction can cause multiple edges even if $G$ is a simple graph.

Now define $u_n$ to be the number of spanning trees of $G'_n$, where $G'_n$ is the multigraph that arises from $G_n$ by duplicating the edge between $1$ and $n$.

By taking $e$ to be an edge between $1$ and $n$, formula (*) applied to $G_n$ gives you $h_n=h_{n-1}+u_{n-1}$ and applied to $G'_n$ it gives you $u_n=h_n+u_{n-1}$.

Combining this you get $h_n=h_{n-1}+u_{n-1}=h_{n-1}+(h_{n-1}+u_{n-2})=h_{n-1}+h_{n-1}+(h_{n-1}-h_{n-2})$, or $h_n=3h_{n-1}-h_{n-2}$, which is a standard recurrence that you can solve easily.