AFTD Auto-Formalizing Theoretical Domains

simple_graph_triangle_free_unique_neighborhood_neighbors_card_le

theoremverified

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
Used by 1

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

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

    lines 6–7

      classical
      let f : α → α := fun x => if h : ∃ w, G.Adj v w ∧ G.Adj w x then Classical.choose h else x
  2. 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.

    lines 8–15

    uses dif_pos, Classical.choose_spec

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

    lines 16–32

    uses simple_graph_triangle_free_private_neighborhood_neighbor_unique

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

    lines 33–37

    uses Finset.mem_image, SimpleGraph.mem_neighborFinset

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

    lines 38–40

    uses Finset.card_image_of_injOn, Finset.card_le_card, SimpleGraph.card_neighborFinset_eq_degree

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

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