A recurrence problem on the number of spanning trees Here is the given Problem : Let $a_2$$_n$$_+$$_1$ denote the number of spanning trees in the undirected graph $G$ on $2n+1$ vertices foemed from two disjoint paths $P_n$ by adding one vertex adjacent to all vertices in both paths. Prove a compact recurrence relation for $a_2$$_n$$_+$$_1$.
My approach : So both $P_n$ (rename those as left and right paths ) has n vertices , So I add the $2n+1$th vertex and this vertex is adjacent to $2n$ vertices . So each of the spanning trees are like left$P_n \cup \{$one edge joining left $P_n$}$\cup${one edge joining right $P_n$}$\cup$right$P_n$. The left and right $P_n$ part is constant for all the spanning trees. The only difference is that two joining edges. So there are total $n^2$ such spanning trees.So the recurrence relation is $a_2$$_n$$_+$$_3$$=$$a_2$$_n$$_+$$_1$$+2n+1$.
Have I done correct?If not then kindly give me a hint. Thanks for reading.
 A: There are a lot more spanning trees than you’re counting. For instance, if the vertices of one path (in order) are $v_1,v_2,v_3$, and $v_4$, those of the other path (in order) are $u_1,u_2,u_3$, and $u_4$, and the new vertex is $w$, one spanning tree that you have not counted has edges $v_1v_2$, $v_3v_4$, $v_2w$, $v_3w$, $u_1u_2$, $u_2u_3$, $wu_3$, and $wu_4$.
HINT: Erase an arbitrary set of edges of $P_1$; if you erase $k$ edges, this will leave a graph $G_1$ with $k+1$ components, each of which is a path. Similarly, erase an arbitrary set of edges of $P_2$ to leave a graph $G_2$. Let $w$ be the new vertex. Choose one vertex in each component of $G_1$ and one vertex in each component of $G_2$, and erase all edges incident at $w$ except the ones joining $w$ to the chosen vertices. All of the spanning trees of $G$ are produced in this way. You are counting only those in which no edges of $P_1$ or $P_2$ are erased.
Added much later:
This is pretty minimal, so I’m going to expand it to the solution of a slightly simpler problem using just one path on $n$ vertices instead of two, a solution from which the solution to this problem can be derived. Let $b_n$ be the number of spanning trees in the undirected graph $G_n$ on $n+1$ vertices by starting with a path $P$ with vertex set $\{v_1,\ldots,v_n\}$ and edges $\{v_k,v_{k+1}\}$ for $k=1,\ldots,n-1$ and adding a vertex $u$ and edges $\{u,v_k\}$ for $k=1,\ldots,n$; we want to find a recurrence for $b_n$.
Suppose that we add a vertex $v_{n+1}$ adjacent to $u$ and $v_n$ to form a graph $G_{n+1}$. If $T$ is a spanning tree of $G_n$, we can extend it to a spanning tree of $G_{n+1}$ in two ways: we can add the edge $\{u,v_{n+1}\}$, or we can add the edge $\{v_n,v_{n+1}\}$. This accounts for all of the spanning trees of $G_{n+1}$ that do not include both of these edges, so there are $2b_n$ such spanning trees of $G_{n+1}$.
Counting the spanning trees of $G_{n+1}$ that do contain both of the edges $\{u,v_{n+1}\}$ and $\{v_n,v_{n+1}\}$ is a bit harder. Note first that the subgraph of $G_{n+1}$ induced by the vertices $v_1,\ldots,v_{n+1}$ is a path $Q$ with edges $\{v_k,v_{k+1}\}$ for $k=1,\ldots,n$. Now let $T$ be a spanning tree in $G_{n+1}$ that contains both of the edges $\{u,v_{n+1}\}$ and $\{v_n,v_{n+1}\}$. Let $Q'$ be the subgraph of $T$ induced by $\{v_1,\ldots,v_{n+1}\}$; then $Q'$ is a disjoint union of subpaths of $Q$. Let $C$ be the subpath containing $v_{n+1}$, and let $T'$ be the subgraph of $T$ that remains after $C$ and the edge $\{u,v_{n+1}\}$ are removed. If $C$ has $m$ edges, $T'$ is a spanning tree in $G_{n+1-m}$, and every spanning tree in $G_{n+1-m}$ can be obtained in this way; this accounts for another $b_{n+1-m}$ spanning trees in $G_{n+1}$. Finally, $C$ must contain $v_n$ and $v_{n+1}$, so $m$ can assume any integer value from $2$ through $n+1$, and $n+1-m$ runs over the integers $0,1,\ldots,n-1$. Thus, $G_{n+1}$ has $\sum_{k=0}^{n-1}b_k$ spanning trees that contain both of the edges $\{u,v_{n+1}\}$ and $\{v_n,v_{n+1}\}$, and we get the recurrence
$$b_{n+1}=2b_n+\sum_{k=0}^{n-1}b_k\;.\tag{1}$$
We can improve on this, however, by rearranging $(1)$ to observe that
$$b_{n+1}-b_n=\sum_{k=0}^nb_k\;.$$
Shifting the indices down by $1$, we see that
$$b_n-b_{n-1}=\sum_{k=0}^{n-1}b_k\;,$$
and substituting into $(1)$ yields the much nicer compact recurrence
$$b_{n+1}=3b_n-b_{n-1}\;.$$
Incidentally, this sequence is closely related to the Fibonacci numbers: specifically, $b_n=F_{2n}$.
