simple_graph_ramsey_three_ten_forty_nine_regular_outer_edges
In a 9-regular triangle-free simple graph on 40 vertices, for every vertex v the induced subgraph on the vertices outside the closed neighbourhood of v has exactly 99 edges.
Statement
theorem simple_graph_ramsey_three_ten_forty_nine_regular_outer_edges (g : SimpleGraph (Fin 40))
[DecidableRel g.Adj] (htri : g.CliqueFree 3) (hreg : ∀ v, g.degree v = 9) (v : Fin 40) :
(g.induce {u | u ≠ v ∧ ¬ g.Adj v u}).edgeFinset.card = 99- Source
- step towards simple_graph_ramsey_three_ten_forty_of_max_degree_le_nine
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- simple_graph_triangle_free_closed_neighborhood_edge_countIn a finite triangle-free graph, the number of edges induced by the vertices outside the closed neighborhood of v plus the sum of the…
The proof, explained
The proof determines the number of edges outside the closed neighborhood of v by edge counting in a triangle-free regular graph. Because g is 9-regular on 40 vertices, the handshaking lemma implies it has 180 edges in total, while the 9 neighbors of v have degree sum 81. In any triangle-free graph, the neighborhood of v is an independent set, so the edges outside the closed neighborhood and the edges incident to the neighbors partition all edges of the graph, leaving exactly 180 - 81 = 99 edges.
The sum of all vertex degrees in g is 360, which equals twice the total number of edges in g.
Since g has 40 vertices and is 9-regular (by hypothesis hreg), summing the degrees over all vertices gives 40 × 9 = 360. By the handshaking lemma (g.sum_degrees_eq_twice_card_edges), this sum equals twice the cardinality of the edge set of g, so g has 180 edges in total.
uses
g.sum_degrees_eq_twice_card_edgesclassical have hsum : (∑ u, g.degree u) = 360 := by simp [hreg] have htotal := g.sum_degrees_eq_twice_card_edges
The sum of the degrees of all neighbors of v is 81.
By g.card_neighborFinset_eq_degree, the neighborhood of v has cardinality equal to the degree of v, which is 9 by regularity (hreg). Since every neighbor u also has degree 9 by regularity, summing their degrees yields 9 × 9 = 81.
uses
g.card_neighborFinset_eq_degreehave hn : (∑ u ∈ g.neighborFinset v, g.degree u) = 81 := by simp [hreg, g.card_neighborFinset_eq_degree]
The number of edges induced outside the closed neighborhood of v plus the sum of degrees of the neighbors of v equals the total number of edges in g.
Because g is triangle-free (htri), no two neighbors of v share an edge. Applying simple_graph_triangle_free_closed_neighborhood_edge_count expresses the total number of edges of g as the sum of the edges induced on the complement of the closed neighborhood of v and the degrees of the neighbors of v.
uses
simple_graph_triangle_free_closed_neighborhood_edge_counthave hed := simple_graph_triangle_free_closed_neighborhood_edge_count g htri vThe induced subgraph on the vertices outside the closed neighborhood of v has exactly 99 edges.
Combining the equations 2 * |E(g)| = 360 (giving |E(g)| = 180), ∑_{u ∈ N(v)} deg(u) = 81, and |E(g \ N[v])| + ∑_{u ∈ N(v)} deg(u) = |E(g)| yields |E(g \ N[v])| = 180 - 81 = 99. The integer linear arithmetic tactic omega closes the goal.
omega
g.sum_degrees_eq_twice_card_edges- The sum of the degrees of all vertices in the graph equals twice the number of edges (Euler's handshaking lemma).
g.card_neighborFinset_eq_degree- The number of neighbors of a vertex equals its degree.
simple_graph_triangle_free_closed_neighborhood_edge_count- In a triangle-free graph, the number of edges in the subgraph induced outside the closed neighborhood of a vertex v, plus the sum of the degrees of the neighbors of v, equals the total number of edges in the graph.
- Line 5 invokes `classical` to provide decidability instances for finset operations, a Lean formal detail with no mathematical counterpart on paper.
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.
/-- For a 9-regular triangle-free 40-vertex graph, the subgraph induced outside any closed neighbourhood has exactly 99 edges. -/theorem simple_graph_ramsey_three_ten_forty_nine_regular_outer_edges (g : SimpleGraph (Fin 40)) [DecidableRel g.Adj] (htri : g.CliqueFree 3) (hreg : ∀ v, g.degree v = 9) (v : Fin 40) : (g.induce {u | u ≠ v ∧ ¬ g.Adj v u}).edgeFinset.card = 99 := by classical have hsum : (∑ u, g.degree u) = 360 := by simp [hreg] have htotal := g.sum_degrees_eq_twice_card_edges have hn : (∑ u ∈ g.neighborFinset v, g.degree u) = 81 := by simp [hreg, g.card_neighborFinset_eq_degree] have hed := simple_graph_triangle_free_closed_neighborhood_edge_count g htri v omega