AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_free_private_neighborhood_neighbor_unique

theoremverified

In a finite triangle-free graph with no independent k-set, if v has degree k − 1 and vertices x and y both have w as their only neighbor in the neighborhood of v, then x and y are equal.

Statement

theorem simple_graph_triangle_free_private_neighborhood_neighbor_unique {α : Type*} [Fintype α]
    (G : SimpleGraph α) [DecidableRel G.Adj] (k : ℕ)
    (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k)
    (v w x y : α) (hdegree : G.degree v + 1 = k)
    (hvw : G.Adj v w) (hwx : G.Adj w x) (hwy : G.Adj w y)
    (hx : ∀ z, G.Adj v z → G.Adj z x → z = w)
    (hy : ∀ z, G.Adj v z → G.Adj z y → z = w) : x = y
Source
Private-neighbor obstruction for OP-926, derived from neighborhood matching.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

We proceed by contradiction, assuming x ≠ y. Because the graph is triangle-free, x and y cannot be adjacent to v nor to each other, making s = {x, y} an independent set disjoint from the open neighborhood of v. A matching theorem for triangle-free graphs with no independent k-set then yields an injective function f from s to the neighborhood of v matching each vertex to a common neighbor. Since w is the unique common neighbor with v for both x and y, both must map to w under f, forcing x = y by injectivity and contradicting the assumption.

  1. Assume for contradiction that x ≠ y.

    We enable classical reasoning and assume, for contradiction, that x ≠ y (named hne).

    lines 8–9

      classical
      by_contra hne
  2. Neither x nor y is adjacent to v, and x is not adjacent to y.

    If v were adjacent to x, then {v, w, x} would form a triangle because v ~ w, w ~ x, and v ~ x, contradicting the assumption that the graph is triangle-free (htri). Similarly, an edge between v and y would make {v, w, y} a triangle, and an edge between x and y would make {w, x, y} a triangle. Hence, none of these edges can exist.

    lines 10–18

    uses SimpleGraph.is3Clique_iff.mpr

      have hvx : ¬ G.Adj v x := by
        intro h
        exact htri {v, w, x} (SimpleGraph.is3Clique_iff.mpr ⟨v, w, x, hvw, h, hwx, rfl⟩)
      have hvy : ¬ G.Adj v y := by
        intro h
        exact htri {v, w, y} (SimpleGraph.is3Clique_iff.mpr ⟨v, w, y, hvw, h, hwy, rfl⟩)
      have hxy : ¬ G.Adj x y := by
        intro h
        exact htri {w, x, y} (SimpleGraph.is3Clique_iff.mpr ⟨w, x, y, hwx, hwy, h, rfl⟩)
  3. The set s = {x, y} is an independent set.

    We define s as the finite set {x, y}. To show that s is an independent set, consider any two distinct elements a, b ∈ s. Each is either x or y, so one must be x and the other y. Since x and y are not adjacent, no two distinct vertices in s are adjacent.

    lines 19–28

    uses Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff, Set.mem_singleton_iff

      let s : Finset α := {x, y}
      have hs_ind : G.IsIndepSet (↑s : Set α) := by
        intro a ha b hb hab
        simp only [s, Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff,
          Set.mem_singleton_iff] at ha hb
        rcases ha with rfl | rfl <;> rcases hb with rfl | rfl
        · exact absurd rfl hab
        · exact hxy
        · exact fun h => hxy h.symm
        · exact absurd rfl hab
  4. No vertex in s is adjacent to v.

    Any element z ∈ s is either x or y. Since neither x nor y is adjacent to v, no element in s is adjacent to v.

    lines 29–34

    uses Finset.mem_insert, Finset.mem_singleton

      have hs_ns : ∀ z ∈ s, ¬ G.Adj v z := by
        intro z hz
        simp only [s, Finset.mem_insert, Finset.mem_singleton] at hz
        rcases hz with rfl | rfl
        · exact hvx
        · exact hvy
  5. There exists an injective matching from s into the neighborhood of v.

    Because the graph is triangle-free, has no independent k-set, v has degree k − 1, and s is an independent set disjoint from the open neighborhood of v, the lemma simple_graph_triangle_free_independent_neighborhood_matching provides an injection f from the subtype of elements in s into the graph's vertices such that for each u ∈ s, f(u) is adjacent to v and adjacent to u.

    line 35

    uses simple_graph_triangle_free_independent_neighborhood_matching

      obtain ⟨f, hf, hfv⟩ := simple_graph_triangle_free_independent_neighborhood_matching G k htri hfree v hdegree s hs_ind hs_ns
  6. The injection f maps both x and y to w.

    Viewing x and y as elements a and b of the subtype of s, f(a) is a neighbor of v adjacent to x. By hypothesis hx, w is the unique neighbor of v adjacent to x, so f(a) = w. Symmetrically, by hy, f(b) = w.

    lines 36–43

      let a : {z // z ∈ s} := ⟨x, by simp [s]⟩
      let b : {z // z ∈ s} := ⟨y, by simp [s]⟩
      have hfx : f a = w := by
        obtain ⟨h1, h2⟩ := hfv a
        exact hx (f a) h1 h2
      have hfy : f b = w := by
        obtain ⟨h1, h2⟩ := hfv b
        exact hy (f b) h1 h2
  7. x = y, contradicting the assumption x ≠ y.

    Since f(a) = w = f(b) and f is injective, we have a = b. Extracting the underlying values via Subtype.val gives x = y, which contradicts hne.

    lines 44–46

    uses congrArg, Subtype.val

      have heq : a = b := hf (by rw [hfx, hfy])
      have hval : (a : α) = (b : α) := congrArg Subtype.val heq
      exact hne hval
SimpleGraph.is3Clique_iff.mpr
A set of three mutually adjacent vertices forms a 3-clique (a triangle) in the graph.
Finset.coe_insert
Coercing the insertion of an element into a finite set to a set equals inserting the element into the coerced set.
Finset.coe_singleton
Coercing a singleton finite set to a set yields the singleton set.
Set.mem_insert_iff
An element belongs to the insertion of a into s if and only if it equals a or belongs to s.
Set.mem_singleton_iff
An element belongs to a singleton set {b} if and only if it equals b.
Finset.mem_insert
An element belongs to the finite set insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton
An element belongs to the finite singleton set {a} if and only if it equals a.
simple_graph_triangle_free_independent_neighborhood_matching
In a finite triangle-free graph with no independent k-set, if vertex v has degree k − 1 and s is an independent set disjoint from the open neighborhood of v, there is an injective function matching each vertex in s to a neighbor in the open neighborhood of v.
congrArg
Applying a function to equal arguments produces equal results.
Subtype.val
The projection that extracts the underlying value from a subtype element.

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_triangle_free_private_neighborhood_neighbor_unique {α : Type*} [Fintype α]    (G : SimpleGraph α) [DecidableRel G.Adj] (k : ℕ)    (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k)    (v w x y : α) (hdegree : G.degree v + 1 = k)    (hvw : G.Adj v w) (hwx : G.Adj w x) (hwy : G.Adj w y)    (hx : ∀ z, G.Adj v z → G.Adj z x → z = w)    (hy : ∀ z, G.Adj v z → G.Adj z y → z = w) : x = y := by  classical  by_contra hne  have hvx : ¬ G.Adj v x := by    intro h    exact htri {v, w, x} (SimpleGraph.is3Clique_iff.mpr ⟨v, w, x, hvw, h, hwx, rfl⟩)  have hvy : ¬ G.Adj v y := by    intro h    exact htri {v, w, y} (SimpleGraph.is3Clique_iff.mpr ⟨v, w, y, hvw, h, hwy, rfl⟩)  have hxy : ¬ G.Adj x y := by    intro h    exact htri {w, x, y} (SimpleGraph.is3Clique_iff.mpr ⟨w, x, y, hwx, hwy, h, rfl⟩)  let s : Finset α := {x, y}  have hs_ind : G.IsIndepSet (↑s : Set α) := by    intro a ha b hb hab    simp only [s, Finset.coe_insert, Finset.coe_singleton, Set.mem_insert_iff,      Set.mem_singleton_iff] at ha hb    rcases ha with rfl | rfl <;> rcases hb with rfl | rfl    · exact absurd rfl hab    · exact hxy    · exact fun h => hxy h.symm    · exact absurd rfl hab  have hs_ns : ∀ z ∈ s, ¬ G.Adj v z := by    intro z hz    simp only [s, Finset.mem_insert, Finset.mem_singleton] at hz    rcases hz with rfl | rfl    · exact hvx    · exact hvy  obtain ⟨f, hf, hfv⟩ := simple_graph_triangle_free_independent_neighborhood_matching G k htri hfree v hdegree s hs_ind hs_ns  let a : {z // z ∈ s} := ⟨x, by simp [s]⟩  let b : {z // z ∈ s} := ⟨y, by simp [s]⟩  have hfx : f a = w := by    obtain ⟨h1, h2⟩ := hfv a    exact hx (f a) h1 h2  have hfy : f b = w := by    obtain ⟨h1, h2⟩ := hfv b    exact hy (f b) h1 h2  have heq : a = b := hf (by rw [hfx, hfy])  have hval : (a : α) = (b : α) := congrArg Subtype.val heq  exact hne hval
See it in the graphDiscuss this resultChallenge it