AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_graph

def

The simple graph joining distinct vertices that have a common in-neighbor in the digraph.

Statement

def digraph_common_predecessor_graph {α : Type} (D : Digraph α) : SimpleGraph α
Source
Auxiliary graph in arXiv:2610.11517, Proposition 4.3, and the four-cycle minimum-counterexample route.
Verified
02 Nov 2026
Axioms
none listed
Used by 47

Lean source view module on GitHub

def digraph_common_predecessor_graph {α : Type} (D : Digraph α) : SimpleGraph α := {
  Adj := fun u v => u ≠ v ∧ ∃ w, D.Adj w u ∧ D.Adj w v
  symm := by
    constructor
    intro u v h
    obtain ⟨hne, w, hwu, hwv⟩ := h
    exact ⟨hne.symm, w, hwv, hwu⟩
  loopless := by
    constructor
    intro u h
    exact h.1 rfl
}
See it in the graphDiscuss this resultChallenge it