simple_graph_triangle_free_private_neighborhood_neighbor_unique
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
- simple_graph_triangle_free_independent_neighborhood_matchingIn a finite triangle-free graph with no independent set of size k, if v has degree k − 1 and s is an independent set consisting of…
- Used by 1
- simple_graph_triangle_free_unique_neighborhood_neighbors_card_leIn a finite triangle-free graph with no independent k-set, if v has degree k − 1, then any finite set of vertices each having exactly one…
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.
Assume for contradiction that x ≠ y.
We enable classical reasoning and assume, for contradiction, that x ≠ y (named hne).
classical by_contra hneNeither 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.
uses
SimpleGraph.is3Clique_iff.mprhave 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⟩)
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.
uses
Finset.coe_insert,Finset.coe_singleton,Set.mem_insert_iff,Set.mem_singleton_ifflet 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
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.
uses
Finset.mem_insert,Finset.mem_singletonhave 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
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.
uses
simple_graph_triangle_free_independent_neighborhood_matchingobtain ⟨f, hf, hfv⟩ := simple_graph_triangle_free_independent_neighborhood_matching G k htri hfree v hdegree s hs_ind hs_nsThe 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.
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
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.
uses
congrArg,Subtype.valhave 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
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_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