Trees Summary

Graph Theory · Axiom Academy

Let's review the essential concepts and properties of trees in graph theory. Root: A designated vertex from which all paths originate Parent: The vertex immediately above a given vertex in the tree hierarchy Child: A vertex immediately below a parent vertex Leaf: A vertex with no children (terminal vertex) Internal Vertex: A non-leaf vertex in the tree Height: The length of the longest path from root to any leaf Definition: A rooted tree where each vertex has at most 2 children Left & Right Children: The two possible children of each vertex Full Binary Tree: Every vertex has 0 or 2 children (no vertex has exactly 1 child) Complete Binary Tree: All levels are filled except possibly the last, which fills left to right Applications: Binary search trees, expression parsing, decision trees Six Equivalent Characterizations of Trees For a graph G with n vertices, the following are equivalent: Definition 1: G is connected and has no cycles (acyclic) Definition 2: G is connected and has exactly n - 1 edges Definition 3: G is acyclic and has exactly n - 1 edges Definition 4: G is connected and removing any edge disconnects it Definition 5: G has no cycles and adding any edge creates exactly one cycle Definition 6: There exists exactly one path between any two vertices in G Definition: A subgraph that is a tree and includes all vertices of the original graph Existence: A connected graph always has at least one spanning tree Properties: Contains all n vertices and exactly n - 1 edges

This is the written version of the interactive lesson above. See the full Graph Theory course.