AFTD Auto-Formalizing Theoretical Domains

simple_graph_ramsey_three_ten_nonregular_edge_bound_conditional

theoremverified

Let G be a triangle-free graph on 40 vertices of maximum degree at most 9. Suppose that, for every vertex v, the number of edges outside its closed neighborhood plus the sum of degrees of its neighbors equals the total number of edges. Then either G is 9-regular, or some vertex v has degree less than 9 and its closed non-neighborhood has at most 180 minus 9 times the degree of v edges.

Statement

theorem simple_graph_ramsey_three_ten_nonregular_edge_bound_conditional (G : SimpleGraph (Fin 40)) [DecidableRel G.Adj]
    (htri : G.CliqueFree 3) (hmax : ∀ v, G.degree v ≤ 9)
    (hedge : ∀ v : Fin 40,
      (G.induce {u | u ≠ v ∧ ¬ G.Adj v u}).edgeFinset.card +
        (∑ u ∈ G.neighborFinset v, G.degree u) = G.edgeFinset.card) :
    (∀ v, G.degree v = 9) ∨
      ∃ v, G.degree v < 9 ∧
        2 * (G.induce {u | u ≠ v ∧ ¬ G.Adj v u}).edgeFinset.card +
          18 * G.degree v ≤ 360
Source
Weighted-neighborhood and edge accounting reduction for OP-926, https://arxiv.org/abs/2401.00392, Proposition 2.1.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The proof proceeds by case analysis on whether G contains a vertex of degree strictly less than 9. If no such vertex exists, every vertex has degree at least 9, which together with the maximum degree bound of 9 implies that G is 9-regular. Otherwise, assigning each vertex y the weight w(y) = 9 - deg(y) ≥ 0, which is positive somewhere, allows applying a weighted neighborhood lemma for triangle-free graphs to find a vertex v with deg(v) < 9 whose neighborhood receives at most half the total graph weight. Expressing both the neighborhood weight and the total weight in terms of degrees, the handshaking lemma, and the given edge-counting hypothesis converts this weight inequality into the desired edge bound for the non-neighborhood of v.

  1. In the case where some vertex has degree strictly less than 9, it suffices to prove the second disjunct of the theorem.

    We perform a case split on whether there exists a vertex with degree strictly less than 9. Assuming such a vertex exists, we choose to establish the right-hand alternative of the conclusion: finding a vertex v of degree less than 9 whose closed non-neighborhood has at most 180 minus 9 times the degree of v edges (scaled by a factor of 2).

    lines 10–12

      classical
      by_cases hn : ∃ v, G.degree v < 9
      · right
  2. There exists a vertex v with degree less than 9 whose neighborhood receives at most half the total weight under w(y) = 9 - deg(y), reducing the goal to showing 2 * e(v's non-neighborhood) + 18 * deg(v) ≤ 360.

    From the case hypothesis, the weight function w(y) = 9 - deg(y) is strictly positive on at least one vertex. Applying the lemma simple_graph_triangle_free_weighted_low_neighborhood to G and this weight function yields a vertex v with w(v) > 0 (that is, deg(v) < 9) such that 2 * ∑_{y ∈ N(v)} w(y) ≤ ∑_{y} w(y). Choosing this v leaves only the edge-count inequality to be shown.

    lines 13–17

    uses simple_graph_triangle_free_weighted_low_neighborhood

        have hw : ∃ x, 0 < 9 - G.degree x := by
          obtain ⟨x, hx⟩ := hn
          exact ⟨x, by omega⟩
        obtain ⟨v, hv, hweight⟩ := simple_graph_triangle_free_weighted_low_neighborhood G (fun y => 9 - G.degree y) htri hw
        refine ⟨v, by omega, ?_⟩
  3. For any subset s of vertices, the sum of degrees plus the sum of weights 9 - deg(x) over s equals 9 times the size of s.

    Because the maximum degree of G is at most 9, we have deg(x) + (9 - deg(x)) = 9 for every vertex x. Combining the two sums over s using Finset.sum_add_distrib and evaluating the sum of the constant 9 over s yields 9 * |s|.

    lines 18–27

    uses Finset.sum_add_distrib, Finset.sum_congr, mul_comm

        have hparts (s : Finset (Fin 40)) :
            (∑ x ∈ s, G.degree x) + (∑ x ∈ s, (9 - G.degree x)) = 9 * s.card := by
          rw [← Finset.sum_add_distrib]
          calc
            (∑ x ∈ s, (G.degree x + (9 - G.degree x))) = ∑ _x ∈ s, 9 := by
              apply Finset.sum_congr rfl
              intro x hx
              have h := hmax x
              omega
            _ = 9 * s.card := by simp [mul_comm]
  4. The inequality 2 * e(v's non-neighborhood) + 18 * deg(v) ≤ 360 holds for v.

    Applying the degree-weight decomposition to the entire vertex set of size 40 gives ∑_{x} deg(x) + ∑_{x} (9 - deg(x)) = 360. By the handshaking lemma, ∑_{x} deg(x) = 2 * |E|, so the total weight is 360 - 2 * |E|. Applying the decomposition to N(v) gives ∑_{u ∈ N(v)} deg(u) + ∑_{u ∈ N(v)} (9 - deg(u)) = 9 * deg(v). The edge hypothesis on v states that e(v's non-neighborhood) + ∑_{u ∈ N(v)} deg(u) = |E|. Substituting these expressions into the weighted neighborhood inequality 2 * ∑_{u ∈ N(v)} (9 - deg(u)) ≤ ∑_{x} (9 - deg(x)) yields 2 * (9 * deg(v) - |E| + e(v's non-neighborhood)) ≤ 360 - 2 * |E|, which simplifies directly to 2 * e(v's non-neighborhood) + 18 * deg(v) ≤ 360.

    lines 28–35

    uses G.sum_degrees_eq_twice_card_edges, Finset.card_univ, Fintype.card_fin

        have hall := hparts Finset.univ
        have hnei := hparts (G.neighborFinset v)
        have hcard : (G.neighborFinset v).card = G.degree v := rfl
        have hhand := G.sum_degrees_eq_twice_card_edges
        have hed := hedge v
        simp only [Finset.card_univ, Fintype.card_fin] at hall
        rw [hcard] at hnei
        omega
  5. In the case where no vertex has degree strictly less than 9, G is 9-regular.

    If there is no vertex with degree strictly less than 9, then every vertex v has degree at least 9. Combined with the maximum degree hypothesis deg(v) ≤ 9, every vertex must have degree exactly 9.

    lines 36–41

    uses not_exists, not_lt

      · left
        intro v
        have hv := hmax v
        simp only [not_exists, not_lt] at hn
        have hv' := hn v
        omega
simple_graph_triangle_free_weighted_low_neighborhood
In a triangle-free graph with non-negative vertex weights not all zero, there exists a vertex of positive weight whose neighborhood receives at most half the total weight of the graph.
Finset.sum_add_distrib
The sum of two functions over a finite set equals the sum of the first plus the sum of the second.
Finset.sum_congr
Two sums over the same finite set are equal if their terms agree on every element of the set.
mul_comm
Multiplication is commutative: a * b = b * a.
G.sum_degrees_eq_twice_card_edges
The sum of the degrees of all vertices in a finite graph equals twice the total number of edges.
Finset.card_univ
The cardinality of the universal finset of a finite type is equal to the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
not_exists
Negating an existential statement is equivalent to a universal statement of the negation: ¬(∃ x, P x) ↔ ∀ x, ¬P x.
not_lt
In a linear order, ¬(a < b) is equivalent to b ≤ a.

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

theorem simple_graph_ramsey_three_ten_nonregular_edge_bound_conditional (G : SimpleGraph (Fin 40)) [DecidableRel G.Adj]    (htri : G.CliqueFree 3) (hmax : ∀ v, G.degree v ≤ 9)    (hedge : ∀ v : Fin 40,      (G.induce {u | u ≠ v ∧ ¬ G.Adj v u}).edgeFinset.card +        (∑ u ∈ G.neighborFinset v, G.degree u) = G.edgeFinset.card) :    (∀ v, G.degree v = 9) ∨      ∃ v, G.degree v < 9 ∧        2 * (G.induce {u | u ≠ v ∧ ¬ G.Adj v u}).edgeFinset.card +          18 * G.degree v ≤ 360 := by  classical  by_cases hn : ∃ v, G.degree v < 9  · right    have hw : ∃ x, 0 < 9 - G.degree x := by      obtain ⟨x, hx⟩ := hn      exact ⟨x, by omega⟩    obtain ⟨v, hv, hweight⟩ := simple_graph_triangle_free_weighted_low_neighborhood G (fun y => 9 - G.degree y) htri hw    refine ⟨v, by omega, ?_⟩    have hparts (s : Finset (Fin 40)) :        (∑ x ∈ s, G.degree x) + (∑ x ∈ s, (9 - G.degree x)) = 9 * s.card := by      rw [← Finset.sum_add_distrib]      calc        (∑ x ∈ s, (G.degree x + (9 - G.degree x))) = ∑ _x ∈ s, 9 := by          apply Finset.sum_congr rfl          intro x hx          have h := hmax x          omega        _ = 9 * s.card := by simp [mul_comm]    have hall := hparts Finset.univ    have hnei := hparts (G.neighborFinset v)    have hcard : (G.neighborFinset v).card = G.degree v := rfl    have hhand := G.sum_degrees_eq_twice_card_edges    have hed := hedge v    simp only [Finset.card_univ, Fintype.card_fin] at hall    rw [hcard] at hnei    omega  · left    intro v    have hv := hmax v    simp only [not_exists, not_lt] at hn    have hv' := hn v    omega
See it in the graphDiscuss this resultChallenge it