AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_edges_seven_clique

theoremverified

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

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.

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

    lines 8–9

      intro u v huv
      obtain ⟨hne, w, hwu, hwv⟩ := huv
  2. 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).

    lines 10–11

      let S : Finset α := Finset.univ.filter fun x => D.Adj w x
      refine ⟨S, hreg w, ?_, ?_, ?_⟩
  3. 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).

    lines 12–13

      · simp [S, hwu]
      · simp [S, hwv]
  4. 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).

    lines 14–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

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