AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_graph_connected

theoremverified

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
Used by 1

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.

  1. 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).

    lines 7–9

    uses SimpleGraph.Connected.mk, reachable_iff_reflTransGen

      apply SimpleGraph.Connected.mk
      intro u v
      apply ((digraph_common_predecessor_graph D).reachable_iff_reflTransGen u v).2
  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.

    lines 10–16

      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
  3. 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.

    line 17

    uses Relation.ReflTransGen.mono

      exact (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

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)
See it in the graphDiscuss this resultChallenge it