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 by Gilbert Strang.

If you find these posts useful I encourage you to also check out the more current Linear Algebra and Its Applications, Fourth Edition, Dr Strang’s introductory textbook Introduction to Linear Algebra, Fourth Edition and the accompanying free online course, and Dr Strang’s other books.