## Lecture Nine: Trees, part 2

• Recall - a tree is connected graph without circuits
• If G is a connected, undirected graph, then it has a spanning tree T -- a subgraph of G that is a tree, and which contains all the vertices of G. This spanning tree can be found, for example, by depth-first or breadth-first search.
• prop: Every tree is bipartite, planar.
• prop: if G is connected, E* a maximal set of circuit-free edges, then E* is a spanning tree for G. (Pf: if E* not connected, an edge can be added between components, contradicting maximality).
• prop: If G is any connected graph on N vertices, if it has N-1 edges, no circuits, then it is a spanning tree.
• We prove Caley's theorem, that there are n^(n-2) labelled trees of size n - done in text also
• Suppose G is weighted: that is, each edge is assigned a non-negative weight. An important question: what's the least expensive (that is, minimum) spanning tree?
• Two algorithms to find this: Prim - build tree incrementally, starting with cheapest edge, and always adding to this core subtree in assembly the next cheapest edge that doesn't create a circuit and that is adjacent to the core. And Kruskal: Assemble in order of cost, the first n-1 edges that don't create a cycle. Both algorithms produce the MST.
• Key lemma: Given a weighted tree as described above, and let V1 and V2 be any non-trivial partition of the vertices in G. If e is the (a) cheapest edge connecting V1 and V2, then there is an MST which contains it.
• Correctness of Kruskal and Prim follow directly from this. (But: different proof in book)

-- RobbieMoll - 05 Oct 2006

Topic revision: r3 - 2006-10-05 - RobbieMoll    Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding UMass CS EdLab? Send feedback