digraph_common_predecessor_graph_connected
In a nonempty loopless strongly connected digraph in which every arc has a common in-neighbor, the common-predecessor graph is connected.
Statement
theorem digraph_common_predecessor_graph_connected (α : Type) [Nonempty α] (D : Digraph α) (hloop : ∀ v, ¬ D.Adj v v) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hstrong : ∀ u v, Relation.ReflTransGen D.Adj u v) : (digraph_common_predecessor_graph D).Connected
- Source
- Connectivity refinement of the auxiliary-graph argument for OP-110.
- Verified
- 02 Nov 2026
- Axioms
- none — Lean reports it depends on no axioms
- Built on 1
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
- Used by 1
- digraph_balanced_seven_large_forces_four_cycles_conditionalA strongly connected loopless 7-outregular digraph on at least 122 vertices whose indegrees are at most seven has four disjoint directed…
The proof, explained
To show that the common-predecessor graph is connected, it suffices (since the vertex type is nonempty) to prove that any two vertices are connected by a path. The core step shows that every directed arc in D is an edge in the common-predecessor graph: any arc x → y has a common in-neighbor by assumption, and x ≠ y because D is loopless. Since D is strongly connected, any two vertices are connected by a directed path in D, which translates directly into a path in the common-predecessor graph.
To prove connectivity, it suffices to show that any two vertices u and v are related by the reflexive-transitive closure of adjacency in the common-predecessor graph.
Since the vertex type α is nonempty, a simple graph is connected if every pair of vertices is reachable (SimpleGraph.Connected.mk). In turn, reachability between u and v is equivalent to their being related by the reflexive-transitive closure of the adjacency relation (reachable_iff_reflTransGen).
uses
SimpleGraph.Connected.mk,reachable_iff_reflTransGenapply SimpleGraph.Connected.mk intro u v apply ((digraph_common_predecessor_graph D).reachable_iff_reflTransGen u v).2
Every directed arc in D is an edge in the common-predecessor graph (D.Adj ≤ (digraph_common_predecessor_graph D).Adj).
Let x and y be vertices with a directed arc from x to y in D. By the common in-neighbor hypothesis (hdom), there exists some vertex w with arcs to both x and y. Furthermore, x and y must be distinct: if x = y, then the arc would be a self-loop, contradicting the hypothesis that D is loopless (hloop). Thus, x and y satisfy both conditions for adjacency in the common-predecessor graph.
have hsub : D.Adj ≤ (digraph_common_predecessor_graph D).Adj := by intro x y hxy obtain ⟨w, hwx, hwy⟩ := hdom x y hxy refine ⟨?_, w, hwx, hwy⟩ intro h subst y exact hloop x hxy
Vertices u and v are connected by a path in the common-predecessor graph, concluding the proof.
By strong connectivity (hstrong), there exists a directed path from u to v in D. Because every directed arc in D is an edge in the common-predecessor graph (hsub), the monotonicity of reflexive-transitive closures (Relation.ReflTransGen.mono) implies that this path is also a valid path in the common-predecessor graph.
uses
Relation.ReflTransGen.monoexact (Relation.ReflTransGen.mono hsub) u v (hstrong u v)
SimpleGraph.Connected.mk- A simple graph on a nonempty vertex set is connected if it is preconnected (every pair of vertices is reachable).
reachable_iff_reflTransGen- Two vertices in a simple graph are reachable from one another if and only if they are related by the reflexive-transitive closure of the adjacency relation.
Relation.ReflTransGen.mono- The reflexive-transitive closure operation is monotone with respect to relation inclusion.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem digraph_common_predecessor_graph_connected (α : Type) [Nonempty α] (D : Digraph α) (hloop : ∀ v, ¬ D.Adj v v) (hdom : ∀ u v, D.Adj u v → ∃ w, D.Adj w u ∧ D.Adj w v) (hstrong : ∀ u v, Relation.ReflTransGen D.Adj u v) : (digraph_common_predecessor_graph D).Connected := by apply SimpleGraph.Connected.mk intro u v apply ((digraph_common_predecessor_graph D).reachable_iff_reflTransGen u v).2 have hsub : D.Adj ≤ (digraph_common_predecessor_graph D).Adj := by intro x y hxy obtain ⟨w, hwx, hwy⟩ := hdom x y hxy refine ⟨?_, w, hwx, hwy⟩ intro h subst y exact hloop x hxy exact (Relation.ReflTransGen.mono hsub) u v (hstrong u v)