Grinberg-Introduction-Graph-Theory · Problem 5.1
Trees and arborescences
Mathematics — Graph Theory · trees-unique-paths
Problem
Let be a multigraph that has no loops. Assume that there exists a vertex of such that for each vertex of , there is a unique path from to in . Prove that is a tree. [Remark: Pay attention to the quantifiers used here: . This differs from the in Statement T2 of the tree equivalence theorem (Theorem 5.2.4).]Intuitive explanation
The key insight is that "unique path from one special vertex to every other vertex" is actually a stronger condition than it first appears. If every vertex is reachable from via exactly one path, then must be connected and acyclic—the two defining properties of a tree. The trick is showing that the uniqueness of paths from forces the entire graph to have no cycles anywhere, not just along paths from , which then makes connected and cycle-free, hence a tree.
Intuitive explanation
The key insight is that "unique path from one special vertex to every other vertex" is actually a stronger condition than it first appears. If every vertex is reachable from via exactly one path, then must be connected and acyclic—the two defining properties of a tree. The trick is showing that the uniqueness of paths from forces the entire graph to have no cycles anywhere, not just along paths from , which then makes connected and cycle-free, hence a tree.