MTH202 final term handout contents

Part 5 of 5 Β· VU Final Term Exam Prep

⭐ Key Takeaways β†’ 🧠 Quick Revision Questions

MTH202 β€” Discrete Mathematics. An independent study tool β€” not affiliated with VU.

On this page

⭐ Key Takeaways

A spanning tree of a connected graph must contain all vertices and be circuit-free, with exactly n-1 edges for n vertices. Kirchhoff's Matrix-Tree Theorem provides a powerful algebraic method to count spanning trees by computing any cofactor of a modified adjacency matrix. For weighted graphs, minimal spanning trees minimize total edge weight and can be found using Kruskal's algorithm (selecting least-weight edges without creating cycles) or Prim's algorithm (growing from a starting vertex by adding the least-weight connecting edge). Both algorithms are greedy and yield optimal minimal spanning trees, though multiple distinct minimal spanning trees may exist for the same graph.

🧠 Quick Revision Questions

  1. What is the formula for the number of edges to delete from a connected graph with n vertices and e edges to obtain a spanning tree?

  2. In Kirchhoff's Matrix-Tree Theorem, how do you construct matrix M from the adjacency matrix of a graph?

  3. What is the key difference between Kruskal's algorithm and Prim's algorithm for finding minimal spanning trees?

  4. How many non-isomorphic spanning trees does a complete graph Kβ‚„ have?

  5. If addition of an edge during Kruskal's algorithm produces a circuit, what should you do with that edge?