AFTD Auto-Formalizing Theoretical Domains

digraph_trianglefree_deficit_sharp54_certificate

theoremverified

The displayed 54-vertex digraph is loopless, oriented, triangle-free, and arc-dominated. Its total positive outdegree-minus-indegree deficit is four and its repeated common-predecessor incidence count is three.

Statement

theorem digraph_trianglefree_deficit_sharp54_certificate :
    (∀ u, ¬ digraph_trianglefree_deficit_sharp54_graph.Adj u u) ∧
    (∀ u v, digraph_trianglefree_deficit_sharp54_graph.Adj u v →
      ¬ digraph_trianglefree_deficit_sharp54_graph.Adj v u) ∧
    (∀ u v w, digraph_trianglefree_deficit_sharp54_graph.Adj u v →
      digraph_trianglefree_deficit_sharp54_graph.Adj v w →
      ¬ digraph_trianglefree_deficit_sharp54_graph.Adj w u) ∧
    (∀ u v, digraph_trianglefree_deficit_sharp54_graph.Adj u v → ∃ p,
      digraph_trianglefree_deficit_sharp54_graph.Adj p u ∧
      digraph_trianglefree_deficit_sharp54_graph.Adj p v) ∧
    (∑ v : Fin 54, ((Finset.univ.filter fun w => digraph_trianglefree_deficit_sharp54_graph.Adj v w).card -
      (Finset.univ.filter fun w => digraph_trianglefree_deficit_sharp54_graph.Adj w v).card)) = 4 ∧
    ((∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w =>
      digraph_trianglefree_deficit_sharp54_graph.Adj v w).card 2) -
        (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).edgeFinset.card) = 3
Source
Finite equality example for girth-dependent overlap accounting; experiments 13466 and 13467.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The theorem certifies that an explicit 54-vertex digraph satisfies six key properties: looplessness, asymmetry, triangle-freeness, arc-domination, a positive degree deficit of 4, and a repeated common-predecessor count of 3. The first five conditions are established via kernel computation (decide +kernel), using pre-verified lemmas for triangle-freeness and arc-domination. For the final condition, the handshaking lemma implies that the common-predecessor graph has 2276 / 2 = 1138 edges, and subtracting this from the total number of out-neighbor pairs (1141) yields the required deficit of 3, closed by linear integer arithmetic.

  1. Adjacency in the 54-vertex directed graph is decidable

    Unfolding the graph definition reduces adjacency to arithmetic comparisons and finite set membership checks on Fin 54, which typeclass inference synthesizes automatically.

    lines 1–3

    instance sharp54_decAdj : DecidableRel digraph_trianglefree_deficit_sharp54_graph.Adj := by
      intro u v; unfold digraph_trianglefree_deficit_sharp54_graph; infer_instance
    
  2. Adjacency in the common-predecessor graph is decidable

    Two vertices share an in-neighbor if there exists some w adjacent to both; since the vertex set Fin 54 is finite and directed adjacency is decidable, this existential search is decidable by typeclass synthesis.

    lines 4–7

    instance sharp54_cp_decAdj :
        DecidableRel (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).Adj := by
      intro u v; unfold digraph_common_predecessor_graph; infer_instance
    
  3. The sum of neighborhood cardinalities in the common-predecessor graph is 2276 automation

    A finite sum over all 54 vertices of the size of each vertex's neighborhood in the common-predecessor graph evaluates to 2276 by kernel computation.

    lines 8–13

    set_option maxHeartbeats 1000000 in
    theorem sharp54_cp_degree_sum :
        ∑ v : Fin 54, (Finset.univ.filter fun w =>
          (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).Adj v w).card = 2276 := by
      decide +kernel
    
  4. The 54-vertex directed graph is triangle-free automation

    Kernel computation checks all triples of vertices and confirms there is no directed 3-cycle u → v → w → u.

    lines 14–17

    set_option maxHeartbeats 1000000 in
    theorem sharp54_triangle_free : ∀ u v w, digraph_trianglefree_deficit_sharp54_graph.Adj u v → digraph_trianglefree_deficit_sharp54_graph.Adj v w → ¬ digraph_trianglefree_deficit_sharp54_graph.Adj w u := by
      decide +kernel
    
  5. The 54-vertex directed graph is arc-dominated automation

    Kernel computation verifies that for every directed edge u → v, there exists a vertex p with directed edges to both u and v.

    lines 18–21

    set_option maxHeartbeats 1000000 in
    theorem sharp54_arc_dominated : ∀ u v, digraph_trianglefree_deficit_sharp54_graph.Adj u v → ∃ p, digraph_trianglefree_deficit_sharp54_graph.Adj p u ∧ digraph_trianglefree_deficit_sharp54_graph.Adj p v := by
      decide +kernel
    
  6. The graph is loopless, asymmetric, triangle-free, arc-dominated, and has total outdegree-indegree deficit 4

    The first two properties (no self-loops, no 2-cycles) and the fifth property (the sum over all vertices of max(0, outdeg(v) - indeg(v)) is 4) are verified directly by kernel computation. The third (triangle-free) and fourth (arc-dominated) properties are provided by the previously proven lemmas sharp54_triangle_free and sharp54_arc_dominated.

    lines 22–38

    uses sharp54_triangle_free, sharp54_arc_dominated

    theorem digraph_trianglefree_deficit_sharp54_certificate :
        (∀ u, ¬ digraph_trianglefree_deficit_sharp54_graph.Adj u u) ∧
        (∀ u v, digraph_trianglefree_deficit_sharp54_graph.Adj u v →
          ¬ digraph_trianglefree_deficit_sharp54_graph.Adj v u) ∧
        (∀ u v w, digraph_trianglefree_deficit_sharp54_graph.Adj u v →
          digraph_trianglefree_deficit_sharp54_graph.Adj v w →
          ¬ digraph_trianglefree_deficit_sharp54_graph.Adj w u) ∧
        (∀ u v, digraph_trianglefree_deficit_sharp54_graph.Adj u v → ∃ p,
          digraph_trianglefree_deficit_sharp54_graph.Adj p u ∧
          digraph_trianglefree_deficit_sharp54_graph.Adj p v) ∧
        (∑ v : Fin 54, ((Finset.univ.filter fun w => digraph_trianglefree_deficit_sharp54_graph.Adj v w).card -
          (Finset.univ.filter fun w => digraph_trianglefree_deficit_sharp54_graph.Adj w v).card)) = 4 ∧
        ((∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w =>
          digraph_trianglefree_deficit_sharp54_graph.Adj v w).card 2) -
            (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).edgeFinset.card) = 3 := by
      refine ⟨by decide +kernel, by decide +kernel, sharp54_triangle_free, sharp54_arc_dominated,
        by decide +kernel, ?_⟩
  7. In the common-predecessor graph, the sum of vertex degrees is twice the number of edges

    We record the handshaking lemma for the common-predecessor graph, stating that ∑ v, deg(v) = 2 |E(CP)|.

    line 39

    uses sum_degrees_eq_twice_card_edges

      have h1 := (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).sum_degrees_eq_twice_card_edges
  8. The sum of degrees in the common-predecessor graph is 2276

    By rewriting with SimpleGraph.card_neighborFinset_eq_degree and SimpleGraph.neighborFinset_eq_filter, each vertex degree is rewritten as the cardinality of its filtered neighborhood set. Finset.sum_congr then equates the sum of degrees to the sum computed in sharp54_cp_degree_sum, which is 2276.

    lines 40–44

    uses Finset.sum_congr, SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter, sharp54_cp_degree_sum

      have h2 : ∑ v : Fin 54, (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).degree v = 2276 := by
        rw [← sharp54_cp_degree_sum]
        apply Finset.sum_congr rfl
        intro v _
        rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter]
  9. The sum of binomial coefficients of outdegrees is 1141 automation

    For each vertex v, the number of unordered pairs of out-neighbors is binom(outdeg(v), 2). The sum of these values over all 54 vertices is computed by the kernel to be 1141.

    lines 45–46

      have h3 : ∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w => digraph_trianglefree_deficit_sharp54_graph.Adj v w).card 2 = 1141 := by
        decide +kernel
  10. The repeated common-predecessor incidence count is 3 automation

    Since the sum of degrees is 2276, the number of edges in the common-predecessor graph is 2276 / 2 = 1138. Subtracting this from the 1141 pairs of common out-neighbors gives 1141 - 1138 = 3, which omega verifies by linear integer arithmetic.

    line 47

      omega
sum_degrees_eq_twice_card_edges
in any finite simple graph, the sum of vertex degrees equals twice the number of edges
Finset.sum_congr
two finite sums over identical index sets are equal if their terms agree at every index
SimpleGraph.card_neighborFinset_eq_degree
the degree of a vertex in a simple graph equals the cardinality of its neighbor finset
SimpleGraph.neighborFinset_eq_filter
the neighbor finset of a vertex v consists of all vertices w adjacent to v
sharp54_cp_degree_sum
the sum of the neighborhood sizes across all 54 vertices in the common-predecessor graph is 2276
sharp54_triangle_free
the 54-vertex digraph has no directed 3-cycles
sharp54_arc_dominated
every directed edge u → v has a common predecessor p with arcs to both u and v

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

instance sharp54_decAdj : DecidableRel digraph_trianglefree_deficit_sharp54_graph.Adj := by  intro u v; unfold digraph_trianglefree_deficit_sharp54_graph; infer_instanceinstance sharp54_cp_decAdj :    DecidableRel (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).Adj := by  intro u v; unfold digraph_common_predecessor_graph; infer_instanceset_option maxHeartbeats 1000000 intheorem sharp54_cp_degree_sum :    ∑ v : Fin 54, (Finset.univ.filter fun w =>      (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).Adj v w).card = 2276 := by  decide +kernelset_option maxHeartbeats 1000000 intheorem sharp54_triangle_free : ∀ u v w, digraph_trianglefree_deficit_sharp54_graph.Adj u v → digraph_trianglefree_deficit_sharp54_graph.Adj v w → ¬ digraph_trianglefree_deficit_sharp54_graph.Adj w u := by  decide +kernelset_option maxHeartbeats 1000000 intheorem sharp54_arc_dominated : ∀ u v, digraph_trianglefree_deficit_sharp54_graph.Adj u v → ∃ p, digraph_trianglefree_deficit_sharp54_graph.Adj p u ∧ digraph_trianglefree_deficit_sharp54_graph.Adj p v := by  decide +kerneltheorem digraph_trianglefree_deficit_sharp54_certificate :    (∀ u, ¬ digraph_trianglefree_deficit_sharp54_graph.Adj u u) ∧    (∀ u v, digraph_trianglefree_deficit_sharp54_graph.Adj u v →      ¬ digraph_trianglefree_deficit_sharp54_graph.Adj v u) ∧    (∀ u v w, digraph_trianglefree_deficit_sharp54_graph.Adj u v →      digraph_trianglefree_deficit_sharp54_graph.Adj v w →      ¬ digraph_trianglefree_deficit_sharp54_graph.Adj w u) ∧    (∀ u v, digraph_trianglefree_deficit_sharp54_graph.Adj u v → ∃ p,      digraph_trianglefree_deficit_sharp54_graph.Adj p u ∧      digraph_trianglefree_deficit_sharp54_graph.Adj p v) ∧    (∑ v : Fin 54, ((Finset.univ.filter fun w => digraph_trianglefree_deficit_sharp54_graph.Adj v w).card -      (Finset.univ.filter fun w => digraph_trianglefree_deficit_sharp54_graph.Adj w v).card)) = 4 ∧    ((∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w =>      digraph_trianglefree_deficit_sharp54_graph.Adj v w).card 2) -        (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).edgeFinset.card) = 3 := by  refine ⟨by decide +kernel, by decide +kernel, sharp54_triangle_free, sharp54_arc_dominated,    by decide +kernel, ?_⟩  have h1 := (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).sum_degrees_eq_twice_card_edges  have h2 : ∑ v : Fin 54, (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).degree v = 2276 := by    rw [← sharp54_cp_degree_sum]    apply Finset.sum_congr rfl    intro v _    rw [← SimpleGraph.card_neighborFinset_eq_degree, SimpleGraph.neighborFinset_eq_filter]  have h3 : ∑ v : Fin 54, Nat.choose (Finset.univ.filter fun w => digraph_trianglefree_deficit_sharp54_graph.Adj v w).card 2 = 1141 := by    decide +kernel  omega
See it in the graphDiscuss this resultChallenge it