AFTD Auto-Formalizing Theoretical Domains

connected_graph_128_independence_three_large_degree

theoremverified

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.

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

    lines 8–15

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

    lines 16–26

    uses Finset.card_insert_le, SimpleGraph.mem_neighborFinset

      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]
  3. 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.

    lines 27–43

    uses Or.inl, Or.inr

      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))
  4. 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.

    lines 44–46

      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)
  5. 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).

    lines 47–59

    uses Finset.mem_inter.mpr, Or.inr, Finset.card_union_add_card_inter, Finset.card_pos.mpr, Finset.mem_union_left, Or.inl

      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))
  6. 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.

    lines 60–109

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

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

    lines 110–114

    uses Or.inr, Finset.disjoint_left.mp

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

    lines 115–129

      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.

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

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