digraph_common_predecessor_graph_indep_free_four
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
- digraph_125_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 125 vertices with dominated arcs and a cycle in every in-neighborhood contains four…
- digraph_127_four_cycles_under_extremal_and_cycle_criteriaA 7-outregular oriented digraph on 127 vertices with dominated arcs and a cycle in every in-neighborhood contains four disjoint directed…
- 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…
- digraph_126_four_cycles_under_extremal_and_cycle_criteriaA loopless oriented seven-outregular digraph on 126 vertices whose arcs have common predecessors and whose every in-neighborhood contains…
- digraph_125_no_four_cycles_overlap_windowFor a loopless oriented seven-outregular digraph on 125 vertices with dominated arcs, a cycle in each in-neighborhood, and no four…
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.
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).
classical intro t htThe 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.
uses
Finset.equivFinOfCardEq,Subtype.extlet 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
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).
uses
Classical.choose,Classical.choose_speclet 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))
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.
apply hno refine ⟨c, fun i => (hc i).1, ?_⟩
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.
uses
Finset.disjoint_left.mprintro 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.
- On paper, one simply writes an independent set of size four as four distinct vertices {v₀, v₁, v₂, v₃}. In Lean, lines 9–16 explicitly construct a bijection between the finset t and Fin 4 to index the vertices and formally prove that the indexing map is injective.
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_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⟩