simple_graph_ramsey_three_ten_nonregular_edge_bound_conditional
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
- simple_graph_triangle_free_weighted_low_neighborhoodIn any finite triangle-free graph with nonnegative integer vertex weights, if some vertex has positive weight then some positive-weight…
- Used by 1
- simple_graph_ramsey_three_ten_forty_nine_regular_or_low_degreeA triangle-free simple graph on 40 vertices with maximum degree at most 9 is either 9-regular, or it has a vertex v of degree < 9 whose…
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.
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).
classical by_cases hn : ∃ v, G.degree v < 9 · right
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.
uses
simple_graph_triangle_free_weighted_low_neighborhoodhave 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, ?_⟩
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|.
uses
Finset.sum_add_distrib,Finset.sum_congr,mul_commhave 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]
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.
uses
G.sum_degrees_eq_twice_card_edges,Finset.card_univ,Fintype.card_finhave 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
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.
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
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.
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