Spanning Trees and Forests

• Let be a connected graph. A spanning tree is a tree contained in such that it includes all the vertices of .

• A spanning forest is a collection of spanning trees

• (Wilson 9.3) Let be a spanning forest of a connected graph. Each cycle of contains an edge in common with the cotree

• (Wilson 9.3a) Let be a spanning forest. Each cut-set of has an edge in common with

• (Wilson 9.3a.z) Let be a spanning tree of a connected graph. Each cut-set of contains an edge in common with .

• (Wilson 9.3x) Every edge is included in some spanning forest of .

• (Wilson e9.10a) - Let be a set of edges of a graph . If has an edge in common with each spanning forest, then contains a cut-set

  • Intuition: Performing an edge deletion by definition will disconnect . It follows, there must be a minimal set in which is out cut-set.

• (Wilson 33.5) A graph contains edge-disjoint spanning forests if and only if for each subgraph

  where and denote the number of edges of and respectively

Minimum Spanning Forest §

• Let be a connected weighted graph. A Minimum Spanning Tree is a spanning tree wherein the total weight of all the edges in the spanning tree is minimized.

• Let be a weighted graph. The Minimum Spanning Forest is a spanning forest wherein the total weight of all the edges included in the spanning forest is minimized.

• MST Cut Property - for any cut-set , if the weight of an edge is strictly smaller than the weights of all other edges in , then this edge belongs to an MST of the graph.

  • Proof: Suppose there is an MST that does not include . Adding will produce a cycle that contains some other edge . By the hypothesis

    Clearly, is another MST but it will have smaller weight.

• MST Cycle Property - For any cycle in the graph, if the weight of an edge of is larger than any of the individual weights of all other edges of , then this edge is not in the MST.

  • Proof: Let be some MST in .

    Now, performing the deletion yields two subtrees so that the two ends of are now in different subtrees.

    Form as follows. Add some other edge so that

    But we know by the theorem , so is a spanning tree and

    which is a contradiction.

• MST Uniqueness - Let be a Graph with each edge having a distinct weight, there will be one and only one unique minimum spanning tree.

  • Proof: We do a proof by contradiction. Suppose there are in fact two MSTs, and that are distinct.

    Since and are distinct, there must be at least 1 edge that is in one but not the other. Say .

    Since is a spanning tree, adding to introduces some cycle with

    Now has no cycles so there exists an edge in and by extension , that is not in . Call this edge

    Now, in replace edge with edge . Clearly so which is a contradiction since was an MST.

• We can find the MST using Kruskal’s algorithm

Links §

• Wilson

• Trees

• Matroid Theory