Exercise 2.5.13. Given a graph with 4 nodes and 6 edges, what are the spanning trees for the graph (16 in all)?
Answer: The graph has 4 nodes and 6 edges. Assume that the graph is as follows:
- edge 1 from node 1 to node 2
- edge 2 from node 2 to node 3
- edge 3 from node 3 to node 4
- edge 4 from node 4 to node 1
- edge 5 from node 1 to node 3
- edge 6 from node 2 to node 4
This graph is equivalent to a square and its two diagonals, with the first 4 edges (edges 1 through 4) forming the outside of the square and the last 2 edges (edges 5 and 6) forming the diagonals.
Since the graph has 4 nodes, all spanning trees contain 3 edges. The first four spanning trees correspond to the outside edges of the square with one edge removed:
- edge 1, edge 2, edge 3
- edge 2, edge 3, edge 4
- edge 3, edge 4, edge 1
- edge 4, edge 1, edge 2
The next four spanning trees include two adjacent outside edges of the square and one diagonal edge, with the diagonal edge connecting to the node between the two outside edges:
- edge 1, edge 2, edge 6
- edge 2, edge 3, edge 5
- edge 3, edge 4, edge 6
- edge 4, edge 1, edge 5
The next four spanning trees include two opposite outside edges of the square and one diagonal edge connecting the two sides:
- edge 1, edge 3, edge 5
- edge 1, edge 3, edge 6
- edge 2, edge 4, edge 5
- edge 2, edge 4, edge 6
The final four spanning trees include one outside edge of the square and the two diagonal edges:
- edge 1, edge 5, edge 6
- edge 2, edge 6, edge 5
- edge 3, edge 5, edge 6
- edge 4, edge 6, edge 5
NOTE: This continues a series of posts containing worked out exercises from the (out of print) book Linear Algebra and Its Applications, Third Edition
If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition
My Math Homework 