simple_graph_nut_graph_subset_neighbors_has_binary_vector
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.
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.
uses
Matrix.toLin'_apply,Matrix.mulVec_single_one,SimpleGraph.isSymm_adjMatrixprivate 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
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.
obtain ⟨hnull, hall⟩ := hnut refine ⟨G.adjMatrix ℝ u - G.adjMatrix ℝ v, ?_, ?_, ?_, ?_⟩
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.
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]
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.
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
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`).
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 _ _
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.
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
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`).
uses
map_sub,simple_graph_nut_graph_subset_neighbors_has_binary_vector_toLin'_adjMatrix_single,LinearMap.mem_ker,sub_selfset 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]
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.
uses
congr_fun,Pi.sub_apply,Pi.zero_apply,Pi.single_eq_of_ne,Pi.single_eq_same,Ne.symmhave 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
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.
uses
Finset.card_univ,Finset.card_le_three,Finset.exists_mem_notMem_of_card_lt_cardhave 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
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.
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.
- In Step 9, the strict inequality between the size of the set of three vertices and the total number of vertices is discharged by `omega` using the assumption that |V| ≥ 4.
- In Steps 4 and 8, contradictions from arithmetic equalities (such as 1 - 0 = 0 and -2 = 0) are evaluated and closed by `norm_num`.
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.
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