AFTD Auto-Formalizing Theoretical Domains

simple_graph_ramsey_three_ten_forty_nine_regular_outer_edges

theoremverified

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

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.

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

    lines 5–7

    uses g.sum_degrees_eq_twice_card_edges

      classical
      have hsum : (∑ u, g.degree u) = 360 := by simp [hreg]
      have htotal := g.sum_degrees_eq_twice_card_edges
  2. 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.

    lines 8–9

    uses g.card_neighborFinset_eq_degree

      have hn : (∑ u ∈ g.neighborFinset v, g.degree u) = 81 := by
        simp [hreg, g.card_neighborFinset_eq_degree]
  3. 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.

    line 10

    uses simple_graph_triangle_free_closed_neighborhood_edge_count

      have hed := simple_graph_triangle_free_closed_neighborhood_edge_count g htri v
  4. The 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.

    line 11

      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.

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

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