AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_graph_indep_free_four

theoremverified

If each in-neighborhood of a finite digraph contains a directed cycle and the digraph has no four disjoint directed cycles, then its common-predecessor graph has no independent set of size four.

Statement

theorem digraph_common_predecessor_graph_indep_free_four
    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α)
    (hin : ∀ a, ∃ C : Finset α, digraph_directed_cycle_on D C ∧ ∀ v ∈ C, D.Adj v a)
    (hno : ¬ ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧
      Pairwise (fun i j => Disjoint (s i) (s j))) :
    (digraph_common_predecessor_graph D).IndepSetFree 4
Source
The independence argument of arXiv:2610.11517 Proposition 4.3, specialized to four cycles.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
  • digraph_directed_cycle_ons is the vertex set of a directed cycle of D: its vertices can be listed without repetition, at least two of them, each with an arc to the…
Used by 5

The proof, explained

The proof proceeds by contradiction. Assuming the common-predecessor graph has an independent set of size 4, we select a directed cycle in the in-neighborhood of each of the 4 vertices. If any two such cycles shared a vertex, that vertex would be a common predecessor of two distinct independent vertices, making them adjacent and contradicting independence. Therefore, the four directed cycles must be pairwise disjoint, contradicting the assumption that no four such cycles exist.

  1. Assume for contradiction that the common-predecessor graph has an independent set of size 4.

    We assume there exists a set of vertices t that forms an independent set of cardinality 4 in the common-predecessor graph of D, aiming to derive a contradiction (False).

    lines 7–8

      classical
      intro t ht
  2. The vertices of t can be enumerated injectively as f(0), f(1), f(2), f(3).

    Because t has cardinality 4, Finset.equivFinOfCardEq gives a bijection e between the subtype t and Fin 4. Its inverse provides an injective mapping f : Fin 4 → α whose values all lie in t.

    lines 9–16

    uses Finset.equivFinOfCardEq, Subtype.ext

      let e : t ≃ Fin 4 := Finset.equivFinOfCardEq ht.card_eq
      let f : Fin 4 → α := fun i => (e.symm i).val
      have hfmem : ∀ i, f i ∈ t := fun i => (e.symm i).property
      have hfinj : Function.Injective f := by
        intro i j hij
        apply e.symm.injective
        apply Subtype.ext
        exact hij
  3. For each indexed vertex f(i), choose a directed cycle c(i) in its in-neighborhood.

    Applying the hypothesis hin to each vertex f(i), Classical.choose extracts a cycle c(i) such that c(i) is a directed cycle in D and every vertex of c(i) has a directed edge to f(i).

    lines 17–20

    uses Classical.choose, Classical.choose_spec

      let c : Fin 4 → Finset α := fun i => Classical.choose (hin (f i))
      have hc : ∀ i, digraph_directed_cycle_on D (c i) ∧ ∀ v ∈ c i, D.Adj v (f i) := by
        intro i
        exact Classical.choose_spec (hin (f i))
  4. It suffices to show that the four cycles c(0), …, c(3) are pairwise disjoint.

    The hypothesis hno states that D does not contain four pairwise disjoint directed cycles. Supplying the family of cycles c and their cycle proofs reduces the goal to proving that c(i) and c(j) are disjoint whenever i ≠ j.

    lines 21–22

      apply hno
      refine ⟨c, fun i => (hc i).1, ?_⟩
  5. The four cycles c(0), …, c(3) are pairwise disjoint.

    Suppose for contradiction that some c(i) and c(j) share a vertex x with i ≠ j. By injectivity of f, f(i) ≠ f(j). Since t is an independent set in the common-predecessor graph and f(i), f(j) ∈ t, they cannot be adjacent. However, by construction of the cycles, x has a directed edge to f(i) and a directed edge to f(j). Thus x is a common predecessor of f(i) and f(j), which by definition makes them adjacent in the common-predecessor graph—a contradiction.

    lines 23–30

    uses Finset.disjoint_left.mpr

      intro i j hij
      apply Finset.disjoint_left.mpr
      intro x hxi hxj
      have hne : f i ≠ f j := fun h => hij (hfinj h)
      have hn : ¬ (digraph_common_predecessor_graph D).Adj (f i) (f j) :=
        ht.isIndepSet (hfmem i) (hfmem j) hne
      apply hn
      exact ⟨hne, x, (hc i).2 x hxi, (hc j).2 x hxj⟩
Finset.equivFinOfCardEq
A finite set of cardinality n is in bijection with Fin n (the canonical n-element type {0, …, n - 1}).
Subtype.ext
Two elements of a subtype are equal if and only if their underlying values are equal.
Classical.choose
Given an existential statement ∃ x, P x, chooses an arbitrary witness x satisfying P.
Classical.choose_spec
The witness selected by Classical.choose satisfies the property P.
Finset.disjoint_left.mpr
Two finite sets are disjoint if no element belonging to the first belongs to the second.

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_indep_free_four    (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α)    (hin : ∀ a, ∃ C : Finset α, digraph_directed_cycle_on D C ∧ ∀ v ∈ C, D.Adj v a)    (hno : ¬ ∃ s : Fin 4 → Finset α, (∀ i, digraph_directed_cycle_on D (s i)) ∧      Pairwise (fun i j => Disjoint (s i) (s j))) :    (digraph_common_predecessor_graph D).IndepSetFree 4 := by  classical  intro t ht  let e : t ≃ Fin 4 := Finset.equivFinOfCardEq ht.card_eq  let f : Fin 4 → α := fun i => (e.symm i).val  have hfmem : ∀ i, f i ∈ t := fun i => (e.symm i).property  have hfinj : Function.Injective f := by    intro i j hij    apply e.symm.injective    apply Subtype.ext    exact hij  let c : Fin 4 → Finset α := fun i => Classical.choose (hin (f i))  have hc : ∀ i, digraph_directed_cycle_on D (c i) ∧ ∀ v ∈ c i, D.Adj v (f i) := by    intro i    exact Classical.choose_spec (hin (f i))  apply hno  refine ⟨c, fun i => (hc i).1, ?_⟩  intro i j hij  apply Finset.disjoint_left.mpr  intro x hxi hxj  have hne : f i ≠ f j := fun h => hij (hfinj h)  have hn : ¬ (digraph_common_predecessor_graph D).Adj (f i) (f j) :=    ht.isIndepSet (hfmem i) (hfmem j) hne  apply hn  exact ⟨hne, x, (hc i).2 x hxi, (hc j).2 x hxj⟩
See it in the graphDiscuss this resultChallenge it