i)
vertices = {1,2,3,4,5,6}
edges = {12,23,34,45,46,62} 6edges, 6vertices
3
1 2 4 5
6
ii)
vertices = {A,B,C,D,E}
edges = {AB,BC,CD,DA,AC,BD,BE,EC}
A B
E
D C
how can I find how many spanning trees these two graphs have? (answer should be 4 on first and 40 on the second one.)
wouldnt the spanning trees on the first just be {12,23,34,45,46}, {34,45,46,62,21}, {54,46,62,21,23}, {62,21,23,34,45}? since I include all the vertices but dont have a cycle? and since its a subgraph of the original?
and for the second one is there a better way to solve this? can I somehow find how many spanning trees the graph has without drawing every single spanning tree?
Best Answer
You strategy for the first tree is a good one. As soon as you omit an edge from the center cycle, you are left with a tree. There are four possible edges you could omit.
For the second tree, you might consider two cases: vertex $E$ either has degree one or degree two.
If $E$ has degree one, we must choose one of its two incident edges to include in our spanning tree $T$. Since $E$ is going to be a leaf in our tree, the subgraph of $T$ obtained by deleting $E$ from $T$ must also be a tree. In the original graph, the vertices $A$, $B$, $C$, and $D$ are a complete graph on four vertices. You may know a famous theorem of Cayley: the number of labeled spanning trees on $n$ vertices is $n^{n-2}$. Hence, there are $4^{4-2} = 16$ spanning trees on these four vertices. All told, that gives us $2 \cdot 16 = 32$ labeled spanning trees with vertex $E$ as a leaf.
If $E$ has degree two, then there only remain two edges to form the tree. We cannot use the edge $BC$ (this would form a cycle). Since there are only $\binom{5}{2} = 10$ ways to choose the edges, I think I would be inclined to just power through all ten possibilities. You will find that six of them result in a tree in which vertex $E$ has degree two.
Adding everything up, there are $32 + 6 = 38$ spanning trees in the second graph.