• Overview
• Details
• Exercises

Trees are connected acyclic graphs. Spanning trees connect all vertices with minimum edges. In weighted graphs, minimum spanning trees (MSTs) minimize total edge weight and obey cut and cycle properties.

• Tree characterizations: connected + acyclic; |E| = |V| − 1; unique simple path between every pair of vertices.
• Spanning tree: subgraph that is a tree containing all vertices; forests for disconnected graphs.
• MST: a spanning tree of minimum total weight (assume connected, weighted, undirected).
• Cut property: for any cut, the lightest edge crossing a cut that respects current forest is safe for some MST.
• Cycle property: the heaviest edge on any cycle is not in any MST.
• Algorithms: Kruskal (sort edges, union–find), Prim (grow tree via PQ). Both rely on the cut property.
• Uniqueness: if all edge weights are distinct, the MST is unique.

1. Prove that a connected graph with |V| − 1 edges is a tree iff it is acyclic.
2. Use the cut property to justify each step of Kruskal's algorithm on a sample graph.
3. Show that with distinct edge weights, the MST is unique using cut/cycle properties.