## Linear Algebra and Its Applications, Exercise 2.5.13

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 .

This entry was posted in linear algebra. Bookmark the permalink.