connected_graph_128_independence_three_large_degree
Every connected simple graph on 128 vertices with no independent set of size four has a vertex of degree at least 43.
Statement
theorem connected_graph_128_independence_three_large_degree
(G : SimpleGraph (Fin 128)) [DecidableRel G.Adj]
(hconn : G.Connected) (hindep : G.IndepSetFree 4) :
∃ v, 43 ≤ G.degree v- Source
- Elementary closed-neighborhood counting refinement of the auxiliary-graph route for OP-110.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
We argue by contradiction, assuming that every vertex has degree at most 42, which implies that every closed neighborhood N(v) has size at most 43. Because the graph has 128 vertices and is connected, it has diameter at least 2, providing an induced 2-edge path a ~ w ~ b with a and b non-adjacent. The set S = N(a) ∪ N(b) has cardinality at most 43 + 43 - 1 = 85. For any vertex c ∉ S, any vertex d outside S ∪ N(c) would form an independent set of size 4 with {a, b, c}, so S ∪ N(c) must contain all 128 vertices, which forces N(c) to be disjoint from S by cardinalities. Consequently, no edge leaves S, which contradicts the connectedness of G since S contains a but cannot contain all 128 vertices.
Assuming no vertex has degree at least 43, every vertex has degree at most 42.
We assume for contradiction that no vertex has degree at least 43 (lines 8–9). Pushing the negation through the existential quantifier yields that every vertex v has degree strictly less than 43, which by linear integer arithmetic (omega) implies degree(v) ≤ 42.
classical by_contra hbad have hdeg : ∀ v, G.degree v ≤ 42 := by intro v have h := hbad push_neg at h have hv := h v omega
For each vertex v, its closed neighborhood N(v) = {v} ∪ N_G(v) has cardinality at most 43, and y ∈ N(x) if and only if y = x or x is adjacent to y.
We define the closed neighborhood N(v) by inserting v into its set of neighbors in G. Since inserting an element increases cardinality by at most 1 (Finset.card_insert_le) and the neighbor set has size at most 42, linear integer arithmetic (omega) bounds |N(v)| by 43. The membership condition y ∈ N(x) ↔ y = x ∨ G.Adj x y is verified directly by simplifying with SimpleGraph.mem_neighborFinset.
uses
Finset.card_insert_le,SimpleGraph.mem_neighborFinsetlet N : Fin 128 → Finset (Fin 128) := fun v => insert v (G.neighborFinset v) have hN : ∀ v, (N v).card ≤ 43 := by intro v have hc := Finset.card_insert_le v (G.neighborFinset v) have hd := hdeg v change (N v).card ≤ (G.neighborFinset v).card + 1 at hc change (G.neighborFinset v).card ≤ 42 at hd omega have hNmem : ∀ x y, y ∈ N x ↔ y = x ∨ G.Adj x y := by intro x y simp [N, SimpleGraph.mem_neighborFinset]
There exists a vertex x not in the closed neighborhood of 0, so 0 ≠ x and 0 is not adjacent to x.
If all 128 vertices were in N(0), N(0) would equal the entire universe of size 128, contradicting |N(0)| ≤ 43. Thus there exists some vertex x ∉ N(0). Since 0 ∈ N(0) by reflexivity, x cannot be 0, and by the membership characterization of N, 0 is not adjacent to x.
uses
Or.inl,Or.inrhave hne : ∃ x : Fin 128, x ∉ N 0 := by by_contra h push_neg at h have he : N 0 = Finset.univ := by ext x simp [h x] have hc := hN 0 rw [he] at hc norm_num at hc obtain ⟨x, hx⟩ := hne have hxne : (0 : Fin 128) ≠ x := by intro h subst x exact hx ((hNmem 0 0).2 (Or.inl rfl)) have hxadj : ¬ G.Adj 0 x := by intro h exact hx ((hNmem 0 x).2 (Or.inr h))
There exist vertices a, w, b such that a is adjacent to w, w is adjacent to b, but a is not adjacent to b and a ≠ b.
Because G is connected and 0 ≠ x with 0 not adjacent to x, the distance between 0 and x is at least 2. Any shortest path from 0 to x therefore contains two vertices a and b at distance 2, linked by a common neighbor w, so a ~ w and w ~ b while a and b are distinct and non-adjacent.
obtain ⟨p, hp⟩ := (hconn 0 x).exists_path_of_dist obtain ⟨a, w, b, haw, hwb, hab, habne⟩ := p.exists_adj_adj_not_adj_ne hp.2 ((hconn 0 x).one_lt_dist_of_ne_of_not_adj hxne hxadj)
The set S = N(a) ∪ N(b) contains a and has size at most 85.
Because w is adjacent to both a and b, w belongs to N(a) ∩ N(b), so the intersection is nonempty (Finset.card_pos.mpr). By the principle of inclusion-exclusion (Finset.card_union_add_card_inter), |S| = |N(a)| + |N(b)| - |N(a) ∩ N(b)| ≤ 43 + 43 - 1 = 85. In addition, a ∈ N(a) ⊆ S (Finset.mem_union_left).
uses
Finset.mem_inter.mpr,Or.inr,Finset.card_union_add_card_inter,Finset.card_pos.mpr,Finset.mem_union_left,Or.inllet S := N a ∪ N b have hcap : S.card ≤ 85 := by have hi : (N a ∩ N b).Nonempty := by refine ⟨w, Finset.mem_inter.mpr ⟨?_, ?_⟩⟩ · exact (hNmem a w).2 (Or.inr haw) · exact (hNmem b w).2 (Or.inr hwb.symm) have hc := Finset.card_union_add_card_inter (N a) (N b) have hi' := Finset.card_pos.mpr hi have ha := hN a have hb := hN b change S.card + _ = _ at hc omega have haS : a ∈ S := Finset.mem_union_left _ ((hNmem a a).2 (Or.inl rfl))
For every vertex c ∉ S, the closed neighborhood N(c) is disjoint from S.
Since c ∉ S = N(a) ∪ N(b), c is distinct and non-adjacent to both a and b. We show that S ∪ N(c) must be the entire vertex set: if any vertex d were outside S ∪ N(c), then d would be distinct and non-adjacent to a, b, and c. Together with the fact that a, b, c are already pairwise non-adjacent and distinct, {a, b, c, d} would form an independent set of size 4, contradicting the hypothesis hindep. Hence |S ∪ N(c)| = 128. By inclusion-exclusion, |S ∩ N(c)| = |S| + |N(c)| - |S ∪ N(c)| ≤ 85 + 43 - 128 = 0. Therefore S ∩ N(c) is empty (Finset.card_eq_zero.mp), proving that S and N(c) are disjoint.
uses
Finset.mem_union_left,ne_comm,Finset.mem_union_right,Finset.eq_univ_iff_forall.mpr,Finset.coe_insert,Finset.coe_singleton,Set.mem_insert_iff,Set.mem_singleton_iff,Ne.symm,Finset.card_union_add_card_inter,Finset.disjoint_left.mpr,Finset.mem_inter.mpr,Finset.card_eq_zero.mphave hcS : ∀ c ∉ S, Disjoint S (N c) := by intro c hc have hca : c ≠ a ∧ ¬ G.Adj a c := by have hca' : c ∉ N a := by intro h; exact hc (Finset.mem_union_left _ h) simpa [hNmem, ne_comm] using hca' have hcb : c ≠ b ∧ ¬ G.Adj b c := by have hcb' : c ∉ N b := by intro h; exact hc (Finset.mem_union_right _ h) simpa [hNmem, ne_comm] using hcb' have hcover : S ∪ N c = Finset.univ := by apply Finset.eq_univ_iff_forall.mpr intro d by_contra hd have hdS : d ∉ S := fun h => hd (Finset.mem_union_left _ h) have hdN : d ∉ N c := fun h => hd (Finset.mem_union_right _ h) have hda : d ≠ a ∧ ¬ G.Adj a d := by have hda' : d ∉ N a := by intro h; exact hdS (Finset.mem_union_left _ h) simpa [hNmem, ne_comm] using hda' have hdb : d ≠ b ∧ ¬ G.Adj b d := by have hdb' : d ∉ N b := by intro h; exact hdS (Finset.mem_union_right _ h) simpa [hNmem, ne_comm] using hdb' have hdc : d ≠ c ∧ ¬ G.Adj c d := by simpa [hNmem, ne_comm] using hdN have hba : ¬ G.Adj b a := fun h => hab h.symm have hca' : ¬ G.Adj c a := fun h => hca.2 h.symm have hcb' : ¬ G.Adj c b := fun h => hcb.2 h.symm have hda' : ¬ G.Adj d a := fun h => hda.2 h.symm have hdb' : ¬ G.Adj d b := fun h => hdb.2 h.symm have hdc' : ¬ G.Adj d c := fun h => hdc.2 h.symm have hfour : G.IsNIndepSet 4 ({a, b, c, d} : Finset (Fin 128)) := by constructor · intro u hu v hv huv simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] at hu hv rcases hu with rfl | rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl | rfl <;> aesop · simp [habne, hca.1, hcb.1, hda.1, hdb.1, hdc.1, Ne.symm habne, Ne.symm hca.1, Ne.symm hcb.1, Ne.symm hda.1, Ne.symm hdb.1, Ne.symm hdc.1] exact hindep _ hfour have hcN := hN c have hu := Finset.card_union_add_card_inter S (N c) rw [hcover] at hu have huni : (Finset.univ : Finset (Fin 128)).card = 128 := by decide have hi : (S ∩ N c).card = 0 := by omega exact Finset.disjoint_left.mpr (by intro z hz hzc have : z ∈ S ∩ N c := Finset.mem_inter.mpr ⟨hz, hzc⟩ have he : S ∩ N c = ∅ := Finset.card_eq_zero.mp hi simpa [he] using this)
S is closed under graph adjacency: if u ∈ S and u is adjacent to v, then v ∈ S.
Suppose for contradiction that v ∉ S. Then u is adjacent to v, meaning u ∈ N(v). But since v ∉ S, the previous step showed that S and N(v) are disjoint, which contradicts u ∈ S.
uses
Or.inr,Finset.disjoint_left.mphave hclosed : ∀ u ∈ S, ∀ v, G.Adj u v → v ∈ S := by intro u hu v huv by_contra hv have huN : u ∈ N v := (hNmem v u).2 (Or.inr huv.symm) exact Finset.disjoint_left.mp (hcS v hv) hu huN
The existence of a vertex outside S contradicts the connectedness of G.
Since |S| ≤ 85 < 128, there is some vertex z ∉ S. By the connectedness of G, there is a walk p connecting a to z. Since a ∈ S and no edge in G leaves S, an induction along the walk p shows that every vertex along p must lie in S. In particular, z ∈ S, which contradicts z ∉ S.
have hout : ∃ x, x ∉ S := by by_contra h push_neg at h have he : S = Finset.univ := by ext x; simp [h x] rw [he] at hcap norm_num at hcap obtain ⟨z, hz⟩ := hout have hreach := hconn a z obtain ⟨p⟩ := hreach have hwalk : ∀ {u v}, (p : G.Walk u v) → u ∈ S → v ∈ S := by intro u v p induction p with | nil => intro h; exact h | cons h p ih => intro hu; exact ih (hclosed _ hu _ h) exact hz (hwalk p haS)
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most 1: |insert(a, s)| ≤ |s| + 1.
SimpleGraph.mem_neighborFinset- A vertex w is in the neighbor finset of v if and only if v and w are adjacent.
Or.inl- From a proof of P, deduces P ∨ Q.
Or.inr- From a proof of Q, deduces P ∨ Q.
Finset.mem_inter.mpr- If an element belongs to both s and t, it belongs to s ∩ t.
Finset.card_union_add_card_inter- Inclusion-exclusion for two finite sets: |s ∪ t| + |s ∩ t| = |s| + |t|.
Finset.card_pos.mpr- A nonempty finite set has strictly positive cardinality.
Finset.mem_union_left- If an element belongs to s, then it belongs to s ∪ t.
ne_comm- Inequality is symmetric: a ≠ b ↔ b ≠ a.
Finset.mem_union_right- If an element belongs to t, then it belongs to s ∪ t.
Finset.eq_univ_iff_forall.mpr- If every element of the universe belongs to a finite set s, then s is the universal set Finset.univ.
Finset.coe_insert- The coercion of insert(a, s) to a set equals insert(a, ↑s).
Finset.coe_singleton- The coercion of the singleton finset {a} to a set is the singleton set {a}.
Set.mem_insert_iff- An element belongs to insert(a, s) if and only if it equals a or belongs to s.
Set.mem_singleton_iff- An element belongs to {b} if and only if it equals b.
Ne.symm- If a ≠ b, then b ≠ a.
Finset.disjoint_left.mpr- If no element of s belongs to t, then s and t are disjoint.
Finset.card_eq_zero.mp- If a finite set has cardinality 0, it is the empty set.
Finset.disjoint_left.mp- If two finite sets s and t are disjoint, no element of s belongs to t.
- The induction on walks (lines 124–128) establishes that the connected component of vertex a is contained in S, so having no edges between S and its complement contradicts the connectedness of G without relying on the formal definition of connected components.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 0theorem connected_graph_128_independence_three_large_degree (G : SimpleGraph (Fin 128)) [DecidableRel G.Adj] (hconn : G.Connected) (hindep : G.IndepSetFree 4) : ∃ v, 43 ≤ G.degree v := by classical by_contra hbad have hdeg : ∀ v, G.degree v ≤ 42 := by intro v have h := hbad push_neg at h have hv := h v omega let N : Fin 128 → Finset (Fin 128) := fun v => insert v (G.neighborFinset v) have hN : ∀ v, (N v).card ≤ 43 := by intro v have hc := Finset.card_insert_le v (G.neighborFinset v) have hd := hdeg v change (N v).card ≤ (G.neighborFinset v).card + 1 at hc change (G.neighborFinset v).card ≤ 42 at hd omega have hNmem : ∀ x y, y ∈ N x ↔ y = x ∨ G.Adj x y := by intro x y simp [N, SimpleGraph.mem_neighborFinset] have hne : ∃ x : Fin 128, x ∉ N 0 := by by_contra h push_neg at h have he : N 0 = Finset.univ := by ext x simp [h x] have hc := hN 0 rw [he] at hc norm_num at hc obtain ⟨x, hx⟩ := hne have hxne : (0 : Fin 128) ≠ x := by intro h subst x exact hx ((hNmem 0 0).2 (Or.inl rfl)) have hxadj : ¬ G.Adj 0 x := by intro h exact hx ((hNmem 0 x).2 (Or.inr h)) obtain ⟨p, hp⟩ := (hconn 0 x).exists_path_of_dist obtain ⟨a, w, b, haw, hwb, hab, habne⟩ := p.exists_adj_adj_not_adj_ne hp.2 ((hconn 0 x).one_lt_dist_of_ne_of_not_adj hxne hxadj) let S := N a ∪ N b have hcap : S.card ≤ 85 := by have hi : (N a ∩ N b).Nonempty := by refine ⟨w, Finset.mem_inter.mpr ⟨?_, ?_⟩⟩ · exact (hNmem a w).2 (Or.inr haw) · exact (hNmem b w).2 (Or.inr hwb.symm) have hc := Finset.card_union_add_card_inter (N a) (N b) have hi' := Finset.card_pos.mpr hi have ha := hN a have hb := hN b change S.card + _ = _ at hc omega have haS : a ∈ S := Finset.mem_union_left _ ((hNmem a a).2 (Or.inl rfl)) have hcS : ∀ c ∉ S, Disjoint S (N c) := by intro c hc have hca : c ≠ a ∧ ¬ G.Adj a c := by have hca' : c ∉ N a := by intro h; exact hc (Finset.mem_union_left _ h) simpa [hNmem, ne_comm] using hca' have hcb : c ≠ b ∧ ¬ G.Adj b c := by have hcb' : c ∉ N b := by intro h; exact hc (Finset.mem_union_right _ h) simpa [hNmem, ne_comm] using hcb' have hcover : S ∪ N c = Finset.univ := by apply Finset.eq_univ_iff_forall.mpr intro d by_contra hd have hdS : d ∉ S := fun h => hd (Finset.mem_union_left _ h) have hdN : d ∉ N c := fun h => hd (Finset.mem_union_right _ h) have hda : d ≠ a ∧ ¬ G.Adj a d := by have hda' : d ∉ N a := by intro h; exact hdS (Finset.mem_union_left _ h) simpa [hNmem, ne_comm] using hda' have hdb : d ≠ b ∧ ¬ G.Adj b d := by have hdb' : d ∉ N b := by intro h; exact hdS (Finset.mem_union_right _ h) simpa [hNmem, ne_comm] using hdb' have hdc : d ≠ c ∧ ¬ G.Adj c d := by simpa [hNmem, ne_comm] using hdN have hba : ¬ G.Adj b a := fun h => hab h.symm have hca' : ¬ G.Adj c a := fun h => hca.2 h.symm have hcb' : ¬ G.Adj c b := fun h => hcb.2 h.symm have hda' : ¬ G.Adj d a := fun h => hda.2 h.symm have hdb' : ¬ G.Adj d b := fun h => hdb.2 h.symm have hdc' : ¬ G.Adj d c := fun h => hdc.2 h.symm have hfour : G.IsNIndepSet 4 ({a, b, c, d} : Finset (Fin 128)) := by constructor · intro u hu v hv huv simp only [Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff] at hu hv rcases hu with rfl | rfl | rfl | rfl <;> rcases hv with rfl | rfl | rfl | rfl <;> aesop · simp [habne, hca.1, hcb.1, hda.1, hdb.1, hdc.1, Ne.symm habne, Ne.symm hca.1, Ne.symm hcb.1, Ne.symm hda.1, Ne.symm hdb.1, Ne.symm hdc.1] exact hindep _ hfour have hcN := hN c have hu := Finset.card_union_add_card_inter S (N c) rw [hcover] at hu have huni : (Finset.univ : Finset (Fin 128)).card = 128 := by decide have hi : (S ∩ N c).card = 0 := by omega exact Finset.disjoint_left.mpr (by intro z hz hzc have : z ∈ S ∩ N c := Finset.mem_inter.mpr ⟨hz, hzc⟩ have he : S ∩ N c = ∅ := Finset.card_eq_zero.mp hi simpa [he] using this) have hclosed : ∀ u ∈ S, ∀ v, G.Adj u v → v ∈ S := by intro u hu v huv by_contra hv have huN : u ∈ N v := (hNmem v u).2 (Or.inr huv.symm) exact Finset.disjoint_left.mp (hcS v hv) hu huN have hout : ∃ x, x ∉ S := by by_contra h push_neg at h have he : S = Finset.univ := by ext x; simp [h x] rw [he] at hcap norm_num at hcap obtain ⟨z, hz⟩ := hout have hreach := hconn a z obtain ⟨p⟩ := hreach have hwalk : ∀ {u v}, (p : G.Walk u v) → u ∈ S → v ∈ S := by intro u v p induction p with | nil => intro h; exact h | cons h p ih => intro hu; exact ih (hclosed _ hu _ h) exact hz (hwalk p haS)