simple_graph_triangle_free_unique_neighborhood_neighbors_card_le
In 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 neighbor in the neighborhood of v has at most degree(v) vertices.
Statement
theorem simple_graph_triangle_free_unique_neighborhood_neighbors_card_le {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (k : ℕ) (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k) (v : α) (hdegree : G.degree v + 1 = k) (P : Finset α) (hP : ∀ x ∈ P, ∃! w, G.Adj v w ∧ G.Adj w x) : P.card ≤ G.degree v
- 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_private_neighborhood_neighbor_uniqueIn 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…
- Used by 1
- simple_graph_ramsey_three_ten_nine_regular_outer_degree_eight_card_leFor a 9-regular triangle-free graph on 40 vertices with no independent ten-set, the induced graph outside the closed neighborhood of any…
The proof, explained
The proof defines a map f sending each vertex in P to its unique neighbor in the open neighborhood N(v) of v. It proves that f is injective on P: if two vertices x, y ∈ P shared the same neighbor f(x) = f(y) in N(v), this shared vertex would be the unique neighbor in N(v) for both, which is impossible for distinct vertices in a triangle-free graph with no independent k-set where degree(v) = k − 1 (via simple_graph_triangle_free_private_neighborhood_neighbor_unique). Since f maps P injectively into N(v), the cardinality of P is at most |N(v)| = degree(v).
Define a selection function f : α → α that maps each vertex to its neighbor in N(v).
Using classical logic, define f(x) by choosing a witness w adjacent to both v and x whenever such a vertex exists, and returning x otherwise.
classical let f : α → α := fun x => if h : ∃ w, G.Adj v w ∧ G.Adj w x then Classical.choose h else x
For every vertex x in P, f(x) is adjacent to both v and x.
For each x ∈ P, hypothesis hP guarantees that a neighbor w ∈ N(v) of x exists. Since this existential condition holds, the definition of f reduces via dif_pos to the chosen witness Classical.choose, which satisfies the required adjacencies by Classical.choose_spec.
uses
dif_pos,Classical.choose_spechave hf_mem : ∀ x ∈ P, G.Adj v (f x) ∧ G.Adj (f x) x := by intro x hx have hex : ∃ w, G.Adj v w ∧ G.Adj w x := (hP x hx).exists have hf : f x = Classical.choose hex := by simp only [f] rw [dif_pos hex] rw [hf] exact Classical.choose_spec hex
The function f is injective on P.
Suppose x, y ∈ P satisfy f(x) = f(y). Let w = f(y) = f(x); then w is a neighbor of v adjacent to both x and y. By the uniqueness hypothesis hP, any neighbor of x in N(v) must be w, and similarly for y. The lemma simple_graph_triangle_free_private_neighborhood_neighbor_unique then guarantees that x and y cannot be distinct, so x = y.
uses
simple_graph_triangle_free_private_neighborhood_neighbor_uniquehave hf_inj : Set.InjOn f ↑P := by intro x hx y hy hxy have hx' : G.Adj v (f x) ∧ G.Adj (f x) x := hf_mem x hx have hy' : G.Adj v (f y) ∧ G.Adj (f y) y := hf_mem y hy have huniqx : ∀ z, G.Adj v z → G.Adj z x → z = f y := by intro z hvz hzx obtain ⟨w0, hw0, huniq0⟩ := hP x hx have h1 : f x = w0 := huniq0 (f x) ⟨hx'.1, hx'.2⟩ have h2 : z = w0 := huniq0 z ⟨hvz, hzx⟩ rw [h2, ← h1, hxy] have huniqy : ∀ z, G.Adj v z → G.Adj z y → z = f y := by intro z hvz hzy obtain ⟨w0, hw0, huniq0⟩ := hP y hy have h1 : f y = w0 := huniq0 (f y) ⟨hy'.1, hy'.2⟩ have h2 : z = w0 := huniq0 z ⟨hvz, hzy⟩ rw [h2, h1] exact simple_graph_triangle_free_private_neighborhood_neighbor_unique G k htri hfree v (f y) x y hdegree hy'.1 (by rw [← hxy]; exact hx'.2) hy'.2 huniqx huniqy
The image of P under f is contained in the neighborhood of v.
By Finset.mem_image, any element in the image of P has the form f(x) for some x ∈ P. Since v is adjacent to f(x), SimpleGraph.mem_neighborFinset confirms that f(x) belongs to the finite neighborhood of v.
uses
Finset.mem_image,SimpleGraph.mem_neighborFinsethave himage : P.image f ⊆ G.neighborFinset v := by intro w hw rw [Finset.mem_image] at hw obtain ⟨x, hxP, rfl⟩ := hw exact (SimpleGraph.mem_neighborFinset G v (f x)).mpr (hf_mem x hxP).1
The cardinality of P is at most the degree of v.
Because f is injective on P, |P| = |f(P)| by Finset.card_image_of_injOn. Because f(P) ⊆ N(v), |f(P)| ≤ |N(v)| by Finset.card_le_card. Finally, |N(v)| = degree(v) by SimpleGraph.card_neighborFinset_eq_degree, completing the inequality chain.
uses
Finset.card_image_of_injOn,Finset.card_le_card,SimpleGraph.card_neighborFinset_eq_degreecalc P.card = (P.image f).card := (Finset.card_image_of_injOn hf_inj).symm _ ≤ (G.neighborFinset v).card := Finset.card_le_card himage _ = G.degree v := SimpleGraph.card_neighborFinset_eq_degree G v
dif_pos- In a dependent conditional expression `if c then t else e`, if the condition `c` holds, the expression evaluates to `t`.
Classical.choose_spec- Given a proof of an existential statement `∃ x, p x`, the chosen element `Classical.choose` satisfies the predicate `p`.
simple_graph_triangle_free_private_neighborhood_neighbor_unique- In a finite triangle-free graph with no independent set of size k, if a vertex v has degree k − 1, then two vertices x and y cannot share a unique neighbor w in the neighborhood of v; if w ∈ N(v) is the sole neighbor in N(v) of both x and y, then x = y.
Finset.mem_image- An element belongs to the image of a finite set under a function if and only if it is the image of some element in the domain set.
SimpleGraph.mem_neighborFinset- A vertex w belongs to the finite neighbor set of v if and only if v and w are adjacent.
Finset.card_image_of_injOn- If a function is injective on a finite set, the cardinality of the image equals the cardinality of that set.
Finset.card_le_card- If a finite set is a subset of another finite set, its cardinality is at most the cardinality of the superset.
SimpleGraph.card_neighborFinset_eq_degree- The cardinality of the finite neighbor set of a vertex v equals the degree of v.
- The proof uses classical choice to define a global function on all vertices of the graph, though only its behavior on the finite subset P is relevant.
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_unique_neighborhood_neighbors_card_le {α : Type*} [Fintype α] (G : SimpleGraph α) [DecidableRel G.Adj] (k : ℕ) (htri : G.CliqueFree 3) (hfree : Gᶜ.CliqueFree k) (v : α) (hdegree : G.degree v + 1 = k) (P : Finset α) (hP : ∀ x ∈ P, ∃! w, G.Adj v w ∧ G.Adj w x) : P.card ≤ G.degree v := by classical let f : α → α := fun x => if h : ∃ w, G.Adj v w ∧ G.Adj w x then Classical.choose h else x have hf_mem : ∀ x ∈ P, G.Adj v (f x) ∧ G.Adj (f x) x := by intro x hx have hex : ∃ w, G.Adj v w ∧ G.Adj w x := (hP x hx).exists have hf : f x = Classical.choose hex := by simp only [f] rw [dif_pos hex] rw [hf] exact Classical.choose_spec hex have hf_inj : Set.InjOn f ↑P := by intro x hx y hy hxy have hx' : G.Adj v (f x) ∧ G.Adj (f x) x := hf_mem x hx have hy' : G.Adj v (f y) ∧ G.Adj (f y) y := hf_mem y hy have huniqx : ∀ z, G.Adj v z → G.Adj z x → z = f y := by intro z hvz hzx obtain ⟨w0, hw0, huniq0⟩ := hP x hx have h1 : f x = w0 := huniq0 (f x) ⟨hx'.1, hx'.2⟩ have h2 : z = w0 := huniq0 z ⟨hvz, hzx⟩ rw [h2, ← h1, hxy] have huniqy : ∀ z, G.Adj v z → G.Adj z y → z = f y := by intro z hvz hzy obtain ⟨w0, hw0, huniq0⟩ := hP y hy have h1 : f y = w0 := huniq0 (f y) ⟨hy'.1, hy'.2⟩ have h2 : z = w0 := huniq0 z ⟨hvz, hzy⟩ rw [h2, h1] exact simple_graph_triangle_free_private_neighborhood_neighbor_unique G k htri hfree v (f y) x y hdegree hy'.1 (by rw [← hxy]; exact hx'.2) hy'.2 huniqx huniqy have himage : P.image f ⊆ G.neighborFinset v := by intro w hw rw [Finset.mem_image] at hw obtain ⟨x, hxP, rfl⟩ := hw exact (SimpleGraph.mem_neighborFinset G v (f x)).mpr (hf_mem x hxP).1 calc P.card = (P.image f).card := (Finset.card_image_of_injOn hf_inj).symm _ ≤ (G.neighborFinset v).card := Finset.card_le_card himage _ = G.degree v := SimpleGraph.card_neighborFinset_eq_degree G v