A graph is acyclic iff paths between vertices are unique
ProvedFamousTheorems.acyclic_iff_paths_unique_7aA graph is acyclic iff paths between vertices are unique. A simple graph has no cycles if and only if for all vertices there is at most one path from to in .
If two distinct paths join and , their union contains a cycle. Conversely, a cycle through and gives two paths between them. It follows that a tree, a connected acyclic graph, has exactly one path between any two vertices. This fact is the basis of rooted trees, spanning-tree algorithms and tree metrics.
Formalization note. Mathlib's SimpleGraph.isAcyclic_iff_subsingleton_path. G.Path u v is the type of walks from to without repeated vertices, and Subsingleton says that it has at most one element.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem acyclic_iff_paths_unique_7a {V : Type*} {G : SimpleGraph V} : G.IsAcyclic ↔ ∀ u v : V, Subsingleton (G.Path u v) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `SimpleGraph.isAcyclic_iff_subsingleton_path`. Proof here reduces to that Mathlib result.