Spanning trees on $P_n$ with an extra off-path vertex.

Question

In West D., Introduction to Graph Theory 2ed 2001, problem 2.2.16 says:

For $n \geq 1$, let $a_n$ be the number of spanning trees in the graph formed from $P_n$ by adding one vertex adjacent to all of $V(P_n)$. For example, $a_1 = 1$, $a_2 = 3$, and $a_3 = 8$. Prove for $n > 1$ that $a_n = a_{n-l} + 1 + \Sigma^{n-1}_{i=1} a_i$. Use this to prove for $n > 2$ that $a_n = 3a_{n-1} - a_{n-2}$ (Comment: It is also possible to argue directly that $a_n = 3a_{n-1} - a_{n-2}$.)

I was able to do the first part, proving the formula with the summation. When attempting to do the second part, I managed to get that each spanning tree counted by $a_{n-1}$ can be extended to a tree for $a_n$ by adding an extra vertex to the end and connecting it either to the last vertex of $P_{n-1}$ or to the off-path vertex, that is, $2*a_{n-1}$ possibilities. (I believe adding the extra edge on either the start or the end of $P_{n-1}$ is the same, should I count them separately?)

The thing is that I don't know where to go from there. I tried using the summation formula, I managed to see that $a_n = 2a_{n-1} + a_{n-2} + \Sigma^{n-3}_{i=1} a_i + 1$, but I can't seem to find an use to that.

Any hint would be appreciated.

Answer 1

The trick for dealing with a recurrence relation that involves a sum like this is to look at two consecutive terms and subtract them: \begin{align} a_n &= 2a_{n-1} + \phantom{1}a_{n-2} + a_{n-3} + a_{n-4} + \dots + a_2 + a_1 + 1 \\ a_{n-1}&= \phantom{0a_{n-1}} + 2a_{n-2} + a_{n-3} + a_{n-4} + \dots + a_2 + a_1 + 1 \\ a_n - a_{n-1} &= 2a_{n-1} - \phantom{1}a_{n-2}. \end{align} This can be rearranged to $a_n = 3a_{n-1} -a_{n-2}$.

---

For completeness, here is the direct argument. Let's denote the vertices of $P_n$ by $v_1, v_2, \dots, v_n$, and the extra vertex by $w$. Let's write $G_n$ for the $(n+1)$-vertex graph with $a_n$ spanning trees.

You are right that we can take each spanning tree of $G_{n-1}$ and add either the edge $v_{n-1} v_n$ or the edge $w v_n$ to get a spanning tree of $G_n$. This can be done in $2a_{n-1}$ ways. Moreover, this describes all spanning trees of $G_n$ which contain exactly one of these edges, because the procedure can be reversed.

The remaining case is: if a spanning tree of $G_{n-1}$ which contains the edge $wv_{n-1}$, then you can delete that edge and instead add both $v_{n-1} v_n$ and $wv_n$. Check that:

1. This always creates a spanning tree of $G_n$; moreover, all spanning trees of $G_n$ which contain both $v_{n-1} v_n$ and $wv_n$ can be obtained in this way.
2. There are $a_{n-1} - a_{n-2}$ spanning trees of $G_{n-1}$ that contain the edge $wv_{n-1}$.

Altogether, $a_n = 2a_{n-1} + (a_{n-1} -a_{n-2}) = 3a_{n-1} - a_{n-2}$.