digraph_common_predecessor_edges_seven_clique
In a 7-outregular finite digraph, every edge of its common-predecessor graph lies in a clique of exactly seven vertices.
Statement
theorem digraph_common_predecessor_edges_seven_clique (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) : ∀ u v, (digraph_common_predecessor_graph D).Adj u v → ∃ S : Finset α, S.card = 7 ∧ u ∈ S ∧ v ∈ S ∧ (digraph_common_predecessor_graph D).IsClique (S : Set α)
- Source
- Out-neighborhood clique structure for the minimum-counterexample route to OP-110.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- 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_common_predecessor_balanced_seven_card_le_121A 7-outregular digraph with indegrees at most seven has at most 121 vertices if its common-predecessor graph is connected and has…
The proof, explained
Given an edge between u and v in the common-predecessor graph, there is by definition a vertex w that is a common predecessor of both vertices in the digraph D. The candidate clique is chosen to be the out-neighborhood S of w, which has cardinality exactly 7 by the 7-outregularity hypothesis. The set S contains both u and v because w has directed edges to each of them. Finally, any two distinct vertices in S share w as a common predecessor, so every pair is adjacent in the common-predecessor graph, making S a 7-clique containing the edge.
The adjacent vertices u and v share a common predecessor w in the digraph.
We introduce the vertices u and v and the hypothesis that they are adjacent in the common-predecessor graph (line 8). By definition of this graph, adjacency means u ≠ v and there is a vertex w with directed edges w → u and w → v in D (line 9).
intro u v huv obtain ⟨hne, w, hwu, hwv⟩ := huv
The out-neighborhood S of w has size 7, reducing the problem to showing that u ∈ S, v ∈ S, and that S is a clique.
Define S to be the finite set of out-neighbors of w (line 10). By the 7-outregularity hypothesis (hreg w), S has cardinality exactly 7. Providing S and its cardinality reduces the proof to three remaining goals: u ∈ S, v ∈ S, and that S is a clique in the common-predecessor graph (line 11).
let S : Finset α := Finset.univ.filter fun x => D.Adj w x refine ⟨S, hreg w, ?_, ?_, ?_⟩
Both u and v belong to S.
Since w → u and w → v were established when obtaining w, both u and v satisfy the defining condition of S = {x | D.Adj w x}, which simplification verifies using hypotheses hwu and hwv (lines 12 and 13).
· simp [S, hwu] · simp [S, hwv]
The set S forms a clique in the common-predecessor graph.
To show that S is a clique, consider any two distinct vertices x, y ∈ S (line 14). By definition of S, both x and y are out-neighbors of w in D (lines 15 and 16, using Finset.mem_filter.mp). Since x ≠ y and w is a common predecessor of both, x and y are adjacent in the common-predecessor graph (line 17).
uses
Finset.mem_filter.mp· intro x hx y hy hxy have hwx : D.Adj w x := (Finset.mem_filter.mp hx).2 have hwy : D.Adj w y := (Finset.mem_filter.mp hy).2 exact ⟨hxy, w, hwx, hwy⟩
Finset.mem_filter.mp- If an element belongs to a filtered finite set `Finset.filter p s`, then it belongs to `s` and satisfies the predicate `p`.
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_edges_seven_clique (α : Type) [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7) : ∀ u v, (digraph_common_predecessor_graph D).Adj u v → ∃ S : Finset α, S.card = 7 ∧ u ∈ S ∧ v ∈ S ∧ (digraph_common_predecessor_graph D).IsClique (S : Set α) := by intro u v huv obtain ⟨hne, w, hwu, hwv⟩ := huv let S : Finset α := Finset.univ.filter fun x => D.Adj w x refine ⟨S, hreg w, ?_, ?_, ?_⟩ · simp [S, hwu] · simp [S, hwv] · intro x hx y hy hxy have hwx : D.Adj w x := (Finset.mem_filter.mp hx).2 have hwy : D.Adj w y := (Finset.mem_filter.mp hy).2 exact ⟨hxy, w, hwx, hwy⟩