Trees and Tree Properties

Math for CS · Axiom Academy

Connected acyclic graphs and their remarkable properties Definition and Equivalent Characterizations This simple definition hides a wealth of equivalent characterizations. The following are all equivalent for a graph T with n vertices: T is connected and acyclic (the definition) T is connected and has exactly n - 1 edges T is acyclic and has exactly n - 1 edges There is exactly one path between any two vertices in T T is connected, but removing any edge disconnects it (minimally connected) T is acyclic, but adding any edge creates exactly one cycle (maximally acyclic) Proof: The average degree in a tree is 2(n-1)/n 2(n-1) — contradiction. So at least 2 leaves exist. Parent: The neighbor of v on the path from v to the root Children: The neighbors of v other than its parent Siblings: Vertices sharing the same parent Ancestor / Descendant: u is an ancestor of v if u is on the path from v to the root Depth: The distance from the root to a vertex (root has depth 0) Height: The maximum depth of any vertex in the tree Subtree: A vertex v and all its descendants Binary trees are the workhorse data structure of computer science. They underlie binary search trees, heaps, Huffman coding, expression parsing, and more. Counting Trees: Cayley's Formula For example, with 4 labeled vertices , there are 4^2 = 16 distinct spanning trees. This elegant formula, proved by Cayley in 1889, can be established via Prufer sequences — a bijection between labeled trees and sequences of length n-2 over .

This is the written version of the interactive lesson above. See the full Math for CS course.