Number of nonisomorphic spanning trees

Question

Graph in question

Are there any spanning trees on this graph? The only way to trace through it is by visiting the and bottom vertices multiple times. Is this legal in forming a spanning a tree from this type of graph?

Thanks!

Answer 1

Quick edit: you might be confused about what a spanning tree is. You don't need to "trace" through your graph (i.e. you don't have to have a Hamiltonian path), as you seem to indicate in your question. Let $G=(V,E)$ be a graph, then $T=(V_T, E_T)$ is a spanning tree of $G$ if $T$ is a subgraph of $G$ and $T$ is a tree. You can define a tree as either (i) a connected acylic graph or (ii) a graph with a unique path between every pair of vertices. We'll make use of both of these equivalent definitions in our answer.

You can show that every connected graph must have at least one spanning tree. In fact, Kirchhoff's Theorem states that the number of spanning trees of $G$ is equal to any cofactor of the Laplacian matrix of $G$. While this is an exciting and beautiful result—in fact, one of my favorite results in spectral graph theory—it doesn't tell us about the number of non-isomorphic spanning trees of $G$.

The graph you posted has exactly 3 non-isomorphic spanning trees. In fact, we can show a slightly more general result. Let $G=(V,E)$ be a graph with vertex set $V = \{a, b, u_1, \dots u_k\}$ and edges between $a, u_i$ and $b, u_i$ for each $i=1 \dots k$. In your example, $k=6$. A picture of the general case is given below.

$\hskip2in$

For each spanning tree $T$, there is a unique path from $a$ to $b$. Without loss of generality, assume that the path is $a, u_1, b$. Because the spanning tree $T$ is connected and acyclic, the other vertices $u_2 \dots u_k$ are adjacent to either $a$ or $b$, but not both. So now we have to ask ourselves, how many ways can we do this? Well, we can assign 0 of the remaining nodes to $a$ and $k-1$ of them to $b$ or we can assign $1$ of the remaining nodes to $a$ and $k-2$ to $b$, and so on. However, the tree we obtain by assigning $r$ nodes to $a$ and $k-(r+1)$ nodes to $b$ is isomorphic to the one obtained by assigning $k-(r+1)$ nodes to $a$ and $r$ nodes to $b$. So there are $\left \lfloor \frac{k}{2} \right \rfloor $ non-isomorphic spanning trees of $G$. For the case of $k=6$, these trees are given below

$\hskip2in$