digraph_trianglefree_deficit_sharp54_certificate
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
- digraph_trianglefree_deficit_sharp54_graphThe cyclic 53-vertex digraph with out-steps 1, 8, 14, 16, 28, 32, 33, extended by a sink whose predecessors are 0, 1, 17, and 25.
- digraph_common_predecessor_graphThe simple graph joining distinct vertices that have a common in-neighbor in the digraph.
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.
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.
instance sharp54_decAdj : DecidableRel digraph_trianglefree_deficit_sharp54_graph.Adj := by intro u v; unfold digraph_trianglefree_deficit_sharp54_graph; infer_instance
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.
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
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.
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
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.
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
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.
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
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.
uses
sharp54_triangle_free,sharp54_arc_dominatedtheorem 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, ?_⟩
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)|.
uses
sum_degrees_eq_twice_card_edgeshave h1 := (digraph_common_predecessor_graph digraph_trianglefree_deficit_sharp54_graph).sum_degrees_eq_twice_card_edgesThe 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.
uses
Finset.sum_congr,SimpleGraph.card_neighborFinset_eq_degree,SimpleGraph.neighborFinset_eq_filter,sharp54_cp_degree_sumhave 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]
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.
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
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.
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
- Several properties of the 54-vertex graph (looplessness, asymmetry, triangle-freeness, arc-domination, the outdegree-indegree deficit, and two finite sums) are verified by the Lean kernel's computational reflection (`decide +kernel`) rather than explicit manual deductions.
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.
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