Short note: Spanning tree

A spanning tree of a connected graph G is a subgraph that is a tree and contains all the vertices of G. If G has n vertices, every spanning tree has exactly n − 1 edges; it is obtained by deleting edges to break all cycles while keeping the graph connected.

Facts:

• A graph has a spanning tree if and only if it is connected.
• A connected graph may have many spanning trees; the complete graph Kₙ has n^(n−2) of them (Cayley).
• A tree has a unique spanning tree, itself.

Finding one: depth-first search or breadth-first search, or by removing an edge from each cycle in turn.

Minimum spanning tree (MST): in a weighted graph, the spanning tree of least total weight.

• Kruskal: sort edges by weight, add the smallest edge that does not form a cycle, until n − 1 edges are chosen.
• Prim: start from a vertex and repeatedly add the cheapest edge from the tree to a new vertex.

Example: triangle a, b, c with edges ab = 1, bc = 2, ca = 3 has three spanning trees (any two edges); the MST is {ab, bc} with weight 3.

Applications: laying cable, pipelines or roads at least cost, network broadcasting and spanning-tree protocol, clustering.