AFTD Auto-Formalizing Theoretical Domains

digraph_common_predecessor_balanced_seven_card_le_121

theoremverified

A 7-outregular digraph with indegrees at most seven has at most 121 vertices if its common-predecessor graph is connected and has independence number at most three.

Statement

theorem digraph_common_predecessor_balanced_seven_card_le_121 (α : Type) [Fintype α] [DecidableEq α]
    (D : Digraph α) [DecidableRel D.Adj]
    (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7)
    (hinde : ∀ v, (Finset.univ.filter fun w => D.Adj w v).card ≤ 7)
    (hconn : (digraph_common_predecessor_graph D).Connected)
    (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) :
    Fintype.card α ≤ 121
Source
Auxiliary-graph transfer and counting steps for the OP-110 campaign.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
Used by 1

The proof, explained

The proof reduces the vertex bound to an established result for simple graphs, `connected_graph_indep_three_degree_42_seven_cliques_card_le_121`, applied to the common-predecessor graph of the digraph D. In this graph, two vertices are adjacent if they share an in-neighbor; because D is 7-outregular with indegrees at most 7, each vertex has degree at most 42, and each edge is contained in the 7-clique formed by the out-neighbors of their shared predecessor. Since the common-predecessor graph is connected and has independence number at most 3, the general bound immediately yields that the digraph has at most 121 vertices.

  1. Adjacency in the common-predecessor graph of D is decidable. automation

    For any vertices u and v, unfolding the definition of the common-predecessor graph gives the condition u ≠ v ∧ ∃ w, D.Adj w u ∧ D.Adj w v. Since the vertex set is finite and both equality and digraph adjacency are decidable, typeclass inference (`infer_instance`) automatically synthesizes decidability for this bounded existential formula.

    lines 2–4

      intro u v
      unfold digraph_common_predecessor_graph
      infer_instance
  2. The digraph has at most 121 vertices (|α| ≤ 121).

    We apply the general theorem `connected_graph_indep_three_degree_42_seven_cliques_card_le_121` to the common-predecessor graph of D. Connectedness (`hconn`) and independence number at most 3 (`hindep`) are given as assumptions. The maximum degree bound of 42 is provided by `digraph_common_predecessor_seven_bounded_indegree_degree_bound`, and the property that every edge lies in a 7-clique is provided by `digraph_common_predecessor_edges_seven_clique`. Together, these hypotheses imply that |α| ≤ 121.

    lines 13–15

    uses connected_graph_indep_three_degree_42_seven_cliques_card_le_121, digraph_common_predecessor_seven_bounded_indegree_degree_bound, digraph_common_predecessor_edges_seven_clique

      exact connected_graph_indep_three_degree_42_seven_cliques_card_le_121 α
        (digraph_common_predecessor_graph D) hconn hindep (digraph_common_predecessor_seven_bounded_indegree_degree_bound α D hreg hinde)
        (digraph_common_predecessor_edges_seven_clique α D hreg)
connected_graph_indep_three_degree_42_seven_cliques_card_le_121
A connected graph with independence number at most 3, maximum degree at most 42, and every edge contained in a 7-clique has at most 121 vertices.
digraph_common_predecessor_seven_bounded_indegree_degree_bound
In a 7-outregular digraph with indegrees at most 7, every vertex in the common-predecessor graph has degree at most 42.
digraph_common_predecessor_edges_seven_clique
In a 7-outregular digraph, every edge of the common-predecessor graph is contained in a 7-clique formed by the out-neighborhood of their common predecessor.

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

private instance in478_digraph_common_predecessor_balanced_seven_card_le_121_decAdj {α : Type} [Fintype α] [DecidableEq α] (D : Digraph α) [DecidableRel D.Adj] : DecidableRel (digraph_common_predecessor_graph D).Adj := by  intro u v  unfold digraph_common_predecessor_graph  infer_instancetheorem digraph_common_predecessor_balanced_seven_card_le_121 (α : Type) [Fintype α] [DecidableEq α]    (D : Digraph α) [DecidableRel D.Adj]    (hreg : ∀ v, (Finset.univ.filter fun w => D.Adj v w).card = 7)    (hinde : ∀ v, (Finset.univ.filter fun w => D.Adj w v).card ≤ 7)    (hconn : (digraph_common_predecessor_graph D).Connected)    (hindep : (digraph_common_predecessor_graph D).IndepSetFree 4) :    Fintype.card α ≤ 121 := by  exact connected_graph_indep_three_degree_42_seven_cliques_card_le_121 α    (digraph_common_predecessor_graph D) hconn hindep (digraph_common_predecessor_seven_bounded_indegree_degree_bound α D hreg hinde)    (digraph_common_predecessor_edges_seven_clique α D hreg)
See it in the graphDiscuss this resultChallenge it