AFTD Auto-Formalizing Theoretical Domains

simple_graph_nut_graph_subset_neighbors_has_binary_vector

theoremverifiedoriginal

Let G be a finite simple nut graph on a vertex set V of cardinality at least 4. If there exist vertices u and v such that the neighbor set of v is a strict subset of the neighbor set of u, then there exists a non-zero (0,1)-vector in the row space of G.adjMatrix ℝ over ℝ that does not equal any row of G.adjMatrix ℝ.

Statement

theorem simple_graph_nut_graph_subset_neighbors_has_binary_vector
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj]
    (hnut : simple_graph_is_nut_graph G)
    (hcard : 4 ≤ Fintype.card V)
    (u v : V) (hsub : G.neighborSet v ⊂ G.neighborSet u) :
    ∃ y : V → ℝ, (∀ w : V, y w = 0 ∨ y w = 1) ∧ y ≠ 0 ∧
      y ∈ LinearMap.range (Matrix.toLin' (G.adjMatrix ℝ)) ∧
      ∀ l : V, y ≠ G.adjMatrix ℝ l
Related work
arXiv:2611.08244 Thm 4.1
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • simple_graph_is_nut_graphA finite simple graph G is a nut graph if its adjacency matrix over ℝ has nullity 1 and every non-zero vector in the null space has a…

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $G$ be a simple graph on $V$ with decidable adjacency. Suppose: 1. $G$ is a nut graph (i.e., simple_graph_is_nut_graph G), 2. $|V| \ge 4$, 3. $u, v \in V$ are vertices such that the neighbor set of $v$ is a strict (proper) subset of the neighbor set of $u$ ($G.\text{neighborSet } v \subsetneq G.\text{neighborSet } u$). Then there exists a vector $y : V \to \mathbb{R}$ such that: 1. For every $w \in V$, $y(w) = 0$ or $y(w) = 1$ ($y$ is a binary vector), 2. $y \neq 0$, 3. $y$ is in the range of the linear map on $V \to \mathbb{R}$ represented by the adjacency matrix of $G$ over $\mathbb{R}$ (i.e., $y$ is in the column/row space of the adjacency matrix), and 4. For all $l \in V$, $y$ is not equal to the $l$-th row (or column) of the adjacency matrix of $G$ (i.e., $y$ is not the characteristic vector of the neighborhood of any vertex $l$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof constructs the candidate vector y = A_u - A_v, the difference of the adjacency rows of u and v. Since the neighborhood of v is strictly contained in that of u, the coordinates of y take values in {0, 1} and at least one coordinate is 1, so y is a non-zero binary vector in the row space of the adjacency matrix. If y were equal to some row A_l, then the vector x = e_u - e_v - e_l would lie in the kernel of the adjacency matrix. Evaluating at v shows x ≠ 0, yet x is supported on at most three vertices {u, v, l}; since |V| ≥ 4, there is a vertex where x vanishes, which contradicts the nut graph property that every non-zero kernel vector is non-vanishing everywhere.

  1. The linear map associated to the adjacency matrix of G maps the standard basis vector e_w to the w-th row of the adjacency matrix.

    Multiplying the adjacency matrix by the standard basis vector e_w yields its w-th column via `Matrix.toLin'_apply` and `Matrix.mulVec_single_one`. Because the adjacency matrix of a simple graph is symmetric (`SimpleGraph.isSymm_adjMatrix`), this column is identical to the w-th row of the adjacency matrix.

    lines 1–7

    uses Matrix.toLin'_apply, Matrix.mulVec_single_one, SimpleGraph.isSymm_adjMatrix

    private lemma simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single
        {V : Type*} [Fintype V] [DecidableEq V]
        (G : SimpleGraph V) [DecidableRel G.Adj] (w : V) :
        Matrix.toLin' (G.adjMatrix ℝ) (Pi.single w (1 : ℝ)) = G.adjMatrix ℝ w := by
      rw [Matrix.toLin'_apply, Matrix.mulVec_single_one]
      funext i
      exact ((SimpleGraph.isSymm_adjMatrix (α := ℝ) (G := G)).apply i w).symm
  2. Unpack the nut graph hypothesis and propose y = A_u - A_v as the candidate vector, setting up the four conditions to verify.

    From the definition of a nut graph, the adjacency matrix has 1-dimensional kernel (`hnull`) and every non-zero vector in the kernel has everywhere non-zero entries (`hall`). We choose y to be the difference between the u-th and v-th rows of the adjacency matrix, A_u - A_v, and reduce the goal to proving that y is binary, non-zero, in the column space (range) of the matrix, and distinct from every row of the matrix.

    lines 19–20

      obtain ⟨hnull, hall⟩ := hnut
      refine ⟨G.adjMatrix ℝ u - G.adjMatrix ℝ v, ?_, ?_, ?_, ?_⟩
  3. The candidate vector y is a (0,1)-vector: for every vertex w, y(w) ∈ {0, 1}.

    The w-th component is y(w) = A_u(w) - A_v(w). Because the neighborhood of v is a subset of the neighborhood of u, any neighbor of v is also a neighbor of u. We split into cases on whether w is adjacent to v: if w ~ v, then also w ~ u, so y(w) = 1 - 1 = 0; if w is not adjacent to v, we case split on whether w ~ u, yielding y(w) = 1 - 0 = 1 when w ~ u and y(w) = 0 - 0 = 0 otherwise.

    lines 21–31

    uses Pi.sub_apply, SimpleGraph.adjMatrix_apply

      · intro w
        have hmem : G.Adj v w → G.Adj u w := fun hvw => hsub.1 hvw
        by_cases hvw : G.Adj v w
        · have huw := hmem hvw
          left
          simp [Pi.sub_apply, SimpleGraph.adjMatrix_apply, huw, hvw]
        · by_cases huw : G.Adj u w
          · right
            simp [Pi.sub_apply, SimpleGraph.adjMatrix_apply, huw, hvw]
          · left
            simp [Pi.sub_apply, SimpleGraph.adjMatrix_apply, huw, hvw]
  4. The vector y is non-zero (y ≠ 0).

    Suppose for contradiction that y = 0. Since the neighborhood of v is strictly contained in that of u (`Set.exists_of_ssubset`), there is a vertex w_0 adjacent to u but not to v. Evaluating y = 0 at w_0 via `congr_fun` gives A_u(w_0) - A_v(w_0) = 1 - 0 = 1 = 0, which is an immediate contradiction.

    lines 32–37

    uses Set.exists_of_ssubset, congr_fun, Pi.sub_apply, Pi.zero_apply, SimpleGraph.adjMatrix_apply, if_pos, if_neg

      · intro hzero
        obtain ⟨w0, hw0u, hw0v⟩ := Set.exists_of_ssubset hsub
        have h := congr_fun hzero w0
        simp only [Pi.sub_apply, Pi.zero_apply, SimpleGraph.adjMatrix_apply] at h
        rw [if_pos (show G.Adj u w0 from hw0u), if_neg (show ¬ G.Adj v w0 from hw0v)] at h
        norm_num at h
  5. The vector y belongs to the range of the linear map associated to the adjacency matrix.

    By the preliminary lemma, A_u = A(e_u) and A_v = A(e_v). Linearity of the map (`LinearMap.map_sub`) gives y = A_u - A_v = A(e_u - e_v), so y is in the range of the linear map (`LinearMap.mem_range_self`).

    lines 38–41

    uses simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single, LinearMap.map_sub, LinearMap.mem_range_self

      · rw [← simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G u,
            ← simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G v,
            ← LinearMap.map_sub]
        exact LinearMap.mem_range_self _ _
  6. Assume for contradiction that y equals some row A_l of the adjacency matrix, and deduce that u ≠ v.

    Let l be a vertex and assume y = A_l. Since N(v) is strictly contained in N(u), there exists a vertex in N(u) \ N(v) (`Set.exists_of_ssubset`). If u = v, then N(u) = N(v), contradicting the existence of such a vertex; hence u ≠ v.

    lines 42–45

    uses Set.exists_of_ssubset

      · intro l heq
        obtain ⟨w0, hw0u, hw0v⟩ := Set.exists_of_ssubset hsub
        have huv : u ≠ v := by
          intro h; subst h; exact hw0v hw0u
  7. The vector x = e_u - e_v - e_l lies in the kernel of the linear map of the adjacency matrix.

    By linearity (`map_sub`) and the preliminary lemma, applying the adjacency matrix to x yields A(x) = (A_u - A_v) - A_l = y - A_l. Under the assumption y = A_l, this difference is zero (`sub_self`), which means x ∈ ker(A) (`LinearMap.mem_ker`).

    lines 46–55

    uses map_sub, simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single, LinearMap.mem_ker, sub_self

        set x : V → ℝ := Pi.single u (1 : ℝ) - Pi.single v (1 : ℝ) - Pi.single l (1 : ℝ) with hxdef
        have hmap : Matrix.toLin' (G.adjMatrix ℝ) x =
            (G.adjMatrix ℝ u - G.adjMatrix ℝ v) - G.adjMatrix ℝ l := by
          simp only [hxdef]
          rw [map_sub, map_sub,
              simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G u,
              simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G v,
              simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G l]
        have hx_ker : x ∈ LinearMap.ker (Matrix.toLin' (G.adjMatrix ℝ)) := by
          rw [LinearMap.mem_ker, hmap, heq, sub_self]
  8. The kernel vector x is non-zero (x ≠ 0).

    Suppose x = 0. Evaluating x at the vertex v gives x(v) = 0 (`congr_fun`). Because u ≠ v, the u-component e_u(v) is 0 (`Pi.single_eq_of_ne`), while e_v(v) is 1 (`Pi.single_eq_same`). Case splitting on whether l = v gives either 0 - 1 - 1 = -2 = 0 or 0 - 1 - 0 = -1 = 0, both of which are contradictory arithmetic equalities. Hence x ≠ 0.

    lines 56–65

    uses congr_fun, Pi.sub_apply, Pi.zero_apply, Pi.single_eq_of_ne, Pi.single_eq_same, Ne.symm

        have hx_ne : x ≠ 0 := by
          intro hzero
          have h := congr_fun hzero v
          simp only [hxdef, Pi.sub_apply, Pi.zero_apply] at h
          rw [Pi.single_eq_of_ne huv.symm, Pi.single_eq_same] at h
          by_cases hlv : l = v
          · rw [hlv, Pi.single_eq_same] at h
            norm_num at h
          · rw [Pi.single_eq_of_ne (Ne.symm hlv)] at h
            norm_num at h
  9. There exists a vertex w ∈ V distinct from u, v, and l.

    The subset {u, v, l} contains at most 3 elements (`Finset.card_le_three`). Since the total number of vertices |V| is at least 4, the cardinality of {u, v, l} is strictly less than the total cardinality |V| (`Finset.card_univ`). By `Finset.exists_mem_notMem_of_card_lt_card`, there exists a vertex w not in {u, v, l}, so w ≠ u, w ≠ v, and w ≠ l.

    lines 66–75

    uses Finset.card_univ, Finset.card_le_three, Finset.exists_mem_notMem_of_card_lt_card

        have hex : ∃ w : V, w ≠ u ∧ w ≠ v ∧ w ≠ l := by
          have hlt : ({u, v, l} : Finset V).card < (Finset.univ : Finset V).card := by
            rw [Finset.card_univ]
            have h3 := Finset.card_le_three (a := u) (b := v) (c := l)
            omega
          obtain ⟨w, _, hw⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt
          exact ⟨w, (by intro h; exact hw (by simp [h])),
                     (by intro h; exact hw (by simp [h])),
                     (by intro h; exact hw (by simp [h]))⟩
        obtain ⟨w, hwu, hwv, hwl⟩ := hex
  10. The coordinate x(w) equals 0, contradicting the nut graph property and proving that y cannot equal any row of the adjacency matrix.

    Because w is distinct from u, v, and l, all three basis vectors e_u, e_v, e_l vanish at w, so x(w) = 0. But G is a nut graph and x is a non-zero element of the kernel of the adjacency matrix, so by `hall`, every entry of x must be non-zero (x(w) ≠ 0). This contradiction refutes y = A_l for any vertex l.

    lines 76–78

        have hwzero : x w = 0 := by
          simp [hxdef, hwu, hwv, hwl]
        exact (hall x hx_ker hx_ne w) hwzero
Matrix.toLin'_apply
Applying the linear map associated to a matrix M to a vector v is given by matrix-vector multiplication M * v.
Matrix.mulVec_single_one
Multiplying a matrix M by the standard basis vector e_j yields the j-th column of M.
SimpleGraph.isSymm_adjMatrix
The adjacency matrix of a simple graph is symmetric.
Pi.sub_apply
The difference of two functions evaluated at an argument is the difference of their values at that argument.
SimpleGraph.adjMatrix_apply
The (v, w)-entry of the adjacency matrix is 1 if vertices v and w are adjacent, and 0 otherwise.
Set.exists_of_ssubset
If a set s is a strict subset of a set t, there exists an element in t that does not belong to s.
congr_fun
If two functions are equal, their values at any argument are equal.
Pi.zero_apply
The zero function evaluated at any input equals zero.
if_pos
An if-then-else expression evaluates to its first branch when the condition holds.
if_neg
An if-then-else expression evaluates to its second branch when the condition does not hold.
simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single
The linear map associated to the adjacency matrix maps the standard basis vector e_w to the w-th row vector of the adjacency matrix.
LinearMap.map_sub
A linear map preserves subtraction: f(x - y) = f(x) - f(y).
LinearMap.mem_range_self
The image of any element under a linear map belongs to the range of that linear map.
map_sub
A homomorphism preserves subtraction: f(a - b) = f(a) - f(b).
LinearMap.mem_ker
An element lies in the kernel of a linear map if and only if the map sends it to zero.
sub_self
Subtracting any element from itself gives zero: a - a = 0.
Pi.single_eq_of_ne
The standard basis vector supported at i evaluates to 0 at any index i' distinct from i.
Pi.single_eq_same
The standard basis vector supported at i with value x evaluates to x at index i.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Finset.card_le_three
A set containing at most three specified elements has cardinality at most 3.
Finset.exists_mem_notMem_of_card_lt_card
If a finite set s has strictly smaller cardinality than a finite set t, there is an element of t that does not belong to s.

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

private lemma simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (w : V) :    Matrix.toLin' (G.adjMatrix ℝ) (Pi.single w (1 : ℝ)) = G.adjMatrix ℝ w := by  rw [Matrix.toLin'_apply, Matrix.mulVec_single_one]  funext i  exact ((SimpleGraph.isSymm_adjMatrix (α := ℝ) (G := G)).apply i w).symm/-- If a finite simple nut graph on at least 4 vertices has two vertices with strictly nested neighborhoods, it has a non-row binary vector in its adjacency row space. -/theorem simple_graph_nut_graph_subset_neighbors_has_binary_vector    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj]    (hnut : simple_graph_is_nut_graph G)    (hcard : 4 ≤ Fintype.card V)    (u v : V) (hsub : G.neighborSet v ⊂ G.neighborSet u) :    ∃ y : V → ℝ, (∀ w : V, y w = 0 ∨ y w = 1) ∧ y ≠ 0 ∧      y ∈ LinearMap.range (Matrix.toLin' (G.adjMatrix ℝ)) ∧      ∀ l : V, y ≠ G.adjMatrix ℝ l := by  obtain ⟨hnull, hall⟩ := hnut  refine ⟨G.adjMatrix ℝ u - G.adjMatrix ℝ v, ?_, ?_, ?_, ?_⟩  · intro w    have hmem : G.Adj v w → G.Adj u w := fun hvw => hsub.1 hvw    by_cases hvw : G.Adj v w    · have huw := hmem hvw      left      simp [Pi.sub_apply, SimpleGraph.adjMatrix_apply, huw, hvw]    · by_cases huw : G.Adj u w      · right        simp [Pi.sub_apply, SimpleGraph.adjMatrix_apply, huw, hvw]      · left        simp [Pi.sub_apply, SimpleGraph.adjMatrix_apply, huw, hvw]  · intro hzero    obtain ⟨w0, hw0u, hw0v⟩ := Set.exists_of_ssubset hsub    have h := congr_fun hzero w0    simp only [Pi.sub_apply, Pi.zero_apply, SimpleGraph.adjMatrix_apply] at h    rw [if_pos (show G.Adj u w0 from hw0u), if_neg (show ¬ G.Adj v w0 from hw0v)] at h    norm_num at h  · rw [← simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G u,        ← simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G v,        ← LinearMap.map_sub]    exact LinearMap.mem_range_self _ _  · intro l heq    obtain ⟨w0, hw0u, hw0v⟩ := Set.exists_of_ssubset hsub    have huv : u ≠ v := by      intro h; subst h; exact hw0v hw0u    set x : V → ℝ := Pi.single u (1 : ℝ) - Pi.single v (1 : ℝ) - Pi.single l (1 : ℝ) with hxdef    have hmap : Matrix.toLin' (G.adjMatrix ℝ) x =        (G.adjMatrix ℝ u - G.adjMatrix ℝ v) - G.adjMatrix ℝ l := by      simp only [hxdef]      rw [map_sub, map_sub,          simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G u,          simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G v,          simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single G l]    have hx_ker : x ∈ LinearMap.ker (Matrix.toLin' (G.adjMatrix ℝ)) := by      rw [LinearMap.mem_ker, hmap, heq, sub_self]    have hx_ne : x ≠ 0 := by      intro hzero      have h := congr_fun hzero v      simp only [hxdef, Pi.sub_apply, Pi.zero_apply] at h      rw [Pi.single_eq_of_ne huv.symm, Pi.single_eq_same] at h      by_cases hlv : l = v      · rw [hlv, Pi.single_eq_same] at h        norm_num at h      · rw [Pi.single_eq_of_ne (Ne.symm hlv)] at h        norm_num at h    have hex : ∃ w : V, w ≠ u ∧ w ≠ v ∧ w ≠ l := by      have hlt : ({u, v, l} : Finset V).card < (Finset.univ : Finset V).card := by        rw [Finset.card_univ]        have h3 := Finset.card_le_three (a := u) (b := v) (c := l)        omega      obtain ⟨w, _, hw⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt      exact ⟨w, (by intro h; exact hw (by simp [h])),                 (by intro h; exact hw (by simp [h])),                 (by intro h; exact hw (by simp [h]))⟩    obtain ⟨w, hwu, hwv, hwl⟩ := hex    have hwzero : x w = 0 := by      simp [hxdef, hwu, hwv, hwl]    exact (hall x hx_ker hx_ne w) hwzero
See it in the graphDiscuss this resultChallenge it