Tree Definition and Properties

Graph Theory · Axiom Academy

LESSON Tree Definition and Properties Understanding the fundamental structure and characteristics of trees in graph theory 1. Formal Definition: Connected Acyclic Graph Connected: There is a path between every pair of vertices Acyclic: The graph contains no cycles (closed paths) Watch as we build a tree step by step, demonstrating both properties. Notice how adding each edge connects vertices without creating any cycles. 2. Key Property: Exactly n-1 Edges for n Vertices A fundamental property of trees is that a tree with n vertices has exactly n-1 edges. This is the minimum number of edges needed to keep the graph connected, and the maximum number possible without creating a cycle. The animation below demonstrates this property by showing trees with different numbers of vertices. 3. Unique Path Between Any Two Vertices In a tree, there is exactly one path between any pair of vertices. This property follows directly from the tree being connected (at least one path exists) and acyclic (no more than one path can exist, as multiple paths would create a cycle). Watch as we highlight the unique path between different pairs of vertices in a tree. Notice that there is never more than one way to travel from one vertex to another. 4. Adding Any Edge Creates Exactly One Cycle

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