simple_graph_nut_graph_diameter_three_has_binary_vector
Let G be a finite simple nut graph on a finite vertex set. If the diameter of G is 3, then there exists a non-zero (0,1)-vector in the row space of the adjacency matrix of G over ℝ that does not occur as a row of the adjacency matrix.
Statement
theorem simple_graph_nut_graph_diameter_three_has_binary_vector {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hnut : simple_graph_is_nut_graph G) (hdiam : G.diam = 3) : ∃ y : V → ℝ, (∀ v : V, y v = 0 ∨ y v = 1) ∧ y ≠ 0 ∧ y ∈ LinearMap.range (Matrix.toLin' (G.adjMatrix ℝ)) ∧ ∀ u : V, y ≠ G.adjMatrix ℝ u
- Formalizes
- arXiv:2611.08244 Theorem 4.1
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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…
- simple_graph_adj_row_add_is_binary_of_dist_threeFor two vertices at distance 3 in a finite simple graph, the sum of their rows in the adjacency matrix over ℝ is a (0,1)-vector.
- simple_graph_adj_row_add_mem_rangeFor any two vertices u and v of a finite simple graph, the sum of their adjacency matrix rows lies in the row space (the range of the…
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. Assume that: 1. $G$ is a nut graph (that is, the kernel of the linear map given by the adjacency matrix of $G$ over $\mathbb{R}$ has $\mathbb{R}$-dimension 1, and every non-zero vector in this kernel has non-zero entries at all vertices $v \in V$); 2. the diameter of $G$ is 3 ($G.\text{diam} = 3$). Then there exists a vector $y : V \to \mathbb{R}$ such that: 1. $y$ is binary: for all $v \in V$, $y(v) = 0$ or $y(v) = 1$; 2. $y$ is non-zero ($y \ne 0$); 3. $y$ is in the range (column space) of the linear map represented by the real adjacency matrix of $G$; 4. for every vertex $u \in V$, $y$ is not equal to the $u$-th row/column of the adjacency matrix of $G$ (that is, $y$ is not the neighborhood indicator vector of any vertex $u$).
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 as the sum of the adjacency matrix rows of two vertices u and v at maximum distance 3. Since dist(u, v) = 3, u and v have no common neighbors, which ensures y is a non-zero (0, 1)-vector belonging to the row space. If y were equal to a row A_l of the adjacency matrix, the linear combination x = e_u + e_v - e_l would be a non-zero element of the kernel of the adjacency matrix. By the nut graph condition, every entry of x must be non-zero, but evaluating x at the internal vertices of a length-3 walk between u and v reveals a zero coordinate, which provides the desired contradiction.
The linear map of the adjacency matrix sends the standard basis vector at w to the w-th row of the adjacency matrix.
Applying the linear map of matrix A to the indicator vector of w yields the w-th column of A. Since the adjacency matrix is symmetric, its w-th column coincides with its w-th row.
uses
SimpleGraph.isSymm_adjMatrix,Matrix.toLin'_apply,Matrix.mulVec_single_oneset A : Matrix V V ℝ := G.adjMatrix ℝ have hsymm : A.IsSymm := SimpleGraph.isSymm_adjMatrix G rw [Matrix.toLin'_apply, Matrix.mulVec_single_one] funext i exact (hsymm.apply i w).symm
The vertex set is nontrivial, and there exist vertices u and v at distance 3 connected by a walk of length 3.
Because the diameter is 3 (and thus non-zero), the vertex set is nontrivial. There exist vertices u and v whose distance equals the diameter 3. Since their distance is non-zero, they are reachable, and hence there is a walk p connecting them of length 3.
uses
SimpleGraph.nontrivial_of_diam_ne_zero,SimpleGraph.exists_dist_eq_diam,SimpleGraph.Reachable.of_dist_ne_zerohave : Nontrivial V := SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hdiam]; decide) obtain ⟨u, v, hdist⟩ : ∃ u v : V, G.dist u v = 3 := by obtain ⟨u, v, huv⟩ := SimpleGraph.exists_dist_eq_diam (G := G) rw [hdiam] at huv exact ⟨u, v, huv⟩ have hne : G.dist u v ≠ 0 := by omega have hr : G.Reachable u v := SimpleGraph.Reachable.of_dist_ne_zero hne obtain ⟨p, hp⟩ := hr.exists_walk_length_eq_dist rw [hdist] at hp
The walk p consists of three edges with two intermediate vertices w₁ and w₂.
By structural induction on the walk p, lengths 0, 1, and 2 are ruled out because p has length 3, leaving a walk of three consecutive edges u ~ w₁, w₁ ~ w₂, and w₂ ~ v.
rcases p with _ | ⟨hadj1, _ | ⟨hadj2, _ | ⟨hadj3, _ | _⟩⟩⟩ · simp at hp · simp at hp · simp at hp · rename_i w1 w2
The candidate vector y = A_u + A_v is a (0,1)-vector.
Since the distance between u and v is 3, they have no common neighbors. Therefore, for every vertex w, at most one of u and v is adjacent to w, so the sum of their adjacency rows at w is either 0 or 1.
uses
simple_graph_adj_row_add_is_binary_of_dist_threerefine ⟨G.adjMatrix ℝ u + G.adjMatrix ℝ v, ?_, ?_, ?_, ?_⟩ · intro w exact simple_graph_adj_row_add_is_binary_of_dist_three G u v hdist w
The candidate vector y = A_u + A_v is non-zero. automation
Evaluating y at the neighbor w₁ of u gives A_u(w₁) + A_v(w₁) = 1 + A_v(w₁). Since entries are non-negative, this cannot equal 0.
uses
congr_fun,Pi.add_apply,Pi.zero_apply,SimpleGraph.adjMatrix_apply,if_pos· intro hzero have hw := congr_fun hzero w1 simp only [Pi.add_apply, Pi.zero_apply, SimpleGraph.adjMatrix_apply] at hw rw [if_pos hadj1] at hw split_ifs at hw <;> linarith
The candidate vector y lies in the range of the adjacency linear map.
The sum of any two rows of the adjacency matrix lies in the range of the associated linear map.
uses
simple_graph_adj_row_add_mem_range· exact simple_graph_adj_row_add_mem_range G u vAssuming y equals the l-th row A_l, the vertices u, v, w₁, w₂ are distinct. automation
If u = v, their distance would be 0 rather than 3. The edges of the walk ensure w₁ ≠ u, w₁ ≠ w₂, and w₂ ≠ v. Furthermore, if w₁ = v then dist(u, v) ≤ 1, and if w₂ = u then dist(u, v) ≤ 1, both contradicting dist(u, v) = 3.
uses
SimpleGraph.Walk.length_cons,SimpleGraph.Walk.length_nil,zero_add· intro l heq have huv : u ≠ v := by intro h subst h simp at hdist have hw1u : w1 ≠ u := hadj1.ne.symm have hw1v : w1 ≠ v := by intro h subst h have hle := G.dist_le hadj1.toWalk simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil, zero_add] at hle omega have hw2u : w2 ≠ u := by intro h subst h have hle := G.dist_le hadj3.toWalk simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil, zero_add] at hle omega have hw2v : w2 ≠ v := hadj3.ne have hw1w2 : w1 ≠ w2 := hadj2.ne
The difference vector x = e_u + e_v - e_l lies in the kernel of the adjacency matrix.
By linearity and the helper lemma, applying the adjacency map to x produces A_u + A_v - A_l, which evaluates to 0 because y = A_u + A_v = A_l.
uses
LinearMap.mem_ker,map_sub,map_add,simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single,sub_selfset x : V → ℝ := Pi.single u 1 + Pi.single v 1 - Pi.single l 1 have hx_ker : x ∈ LinearMap.ker (Matrix.toLin' (G.adjMatrix ℝ)) := by rw [LinearMap.mem_ker, map_sub, map_add] rw [simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single G u, simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single G v, simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single G l] rw [heq, sub_self]
The vector x is non-zero, so by the nut graph property all its components are non-zero.
If x were zero, evaluating at v (if l = u) or at u (if l ≠ u) would force 1 = 0 since u ≠ v. Thus x ≠ 0, and since G is a nut graph and x is in the kernel, x(w) ≠ 0 for every vertex w.
uses
congr_funhave hx_ne : x ≠ 0 := by intro hzero by_cases hlu : l = u · have hv := congr_fun hzero v subst hlu simp [x] at hv · have hu := congr_fun hzero u simp [x, hlu, huv] at hu have hnut_nz := hnut.2 x hx_ker hx_ne
Evaluating x at w₁ or w₂ yields 0, reaching a contradiction.
Because w₁ ≠ w₂, the vertex l cannot equal both. If l = w₁, then l ≠ w₂, and since w₂ is distinct from u and v, x(w₂) = 0, contradicting the nut graph property. If l ≠ w₁, then x(w₁) = 0, similarly yielding a contradiction. Hence y cannot equal any row of the adjacency matrix.
by_cases hlw1 : l = w1 · have hkw2 : x w2 = 0 := by have : w2 ≠ l := by subst hlw1; exact hw1w2.symm simp [x, hw2u, hw2v, this] exact hnut_nz w2 hkw2 · have hkw1 : x w1 = 0 := by simp [x, hw1u, hw1v, hlw1] exact hnut_nz w1 hkw1
Any remaining walk cases with length strictly greater than 3 are impossible. automation
The remaining case from destructing the walk p requires its length to exceed 3, contradicting p.length = 3.
· simp at hp
SimpleGraph.isSymm_adjMatrix- The adjacency matrix of any simple graph is symmetric.
Matrix.toLin'_apply- Applying the linear map associated with a matrix to a vector equals matrix-vector multiplication.
Matrix.mulVec_single_one- Multiplying a matrix by the standard basis vector with a 1 at index j yields the j-th column of the matrix.
SimpleGraph.nontrivial_of_diam_ne_zero- A graph with non-zero diameter has at least two vertices.
SimpleGraph.exists_dist_eq_diam- In a nonempty graph, there exist vertices whose distance equals the diameter of the graph.
SimpleGraph.Reachable.of_dist_ne_zero- If the distance between two vertices is non-zero, they are reachable from each other.
simple_graph_adj_row_add_is_binary_of_dist_three- For vertices at distance 3 in a simple graph, the sum of their adjacency matrix rows is a (0,1)-vector.
congr_fun- If two functions are equal, their evaluations at any argument are equal.
Pi.add_apply- Pointwise addition of functions evaluated at a point is the sum of their individual values.
Pi.zero_apply- The zero function evaluated at any point yields zero.
SimpleGraph.adjMatrix_apply- Entry (v, w) of the adjacency matrix is 1 if v and w are adjacent and 0 otherwise.
if_pos- If a proposition c is true, then (if c then t else e) equals t.
simple_graph_adj_row_add_mem_range- The sum of two rows of the adjacency matrix belongs to the range of the linear map defined by the adjacency matrix.
SimpleGraph.Walk.length_cons- The length of a walk with an initial edge prepended is 1 plus the length of the remaining walk.
SimpleGraph.Walk.length_nil- The length of an empty walk is 0.
zero_add- Adding 0 on the left is the identity (0 + a = a).
LinearMap.mem_ker- A vector is in the kernel of a linear map if and only if the map sends it to 0.
map_sub- Linear maps preserve subtraction: f(a - b) = f(a) - f(b).
map_add- Linear maps preserve addition: f(a + b) = f(a) + f(b).
simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single- The linear map of the adjacency matrix sends the standard basis vector at w to the w-th row of the adjacency matrix.
sub_self- Subtracting an element from itself yields 0 (a - a = 0).
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.
lemma simple_graph_nut_graph_diameter_three_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 set A : Matrix V V ℝ := G.adjMatrix ℝ have hsymm : A.IsSymm := SimpleGraph.isSymm_adjMatrix G rw [Matrix.toLin'_apply, Matrix.mulVec_single_one] funext i exact (hsymm.apply i w).symm/-- Every finite simple nut graph of diameter 3 has a non-zero (0,1)-vector in its adjacency row space not occurring as a row. -/theorem simple_graph_nut_graph_diameter_three_has_binary_vector {V : Type*} [Fintype V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (hnut : simple_graph_is_nut_graph G) (hdiam : G.diam = 3) : ∃ y : V → ℝ, (∀ v : V, y v = 0 ∨ y v = 1) ∧ y ≠ 0 ∧ y ∈ LinearMap.range (Matrix.toLin' (G.adjMatrix ℝ)) ∧ ∀ u : V, y ≠ G.adjMatrix ℝ u := by have : Nontrivial V := SimpleGraph.nontrivial_of_diam_ne_zero (by rw [hdiam]; decide) obtain ⟨u, v, hdist⟩ : ∃ u v : V, G.dist u v = 3 := by obtain ⟨u, v, huv⟩ := SimpleGraph.exists_dist_eq_diam (G := G) rw [hdiam] at huv exact ⟨u, v, huv⟩ have hne : G.dist u v ≠ 0 := by omega have hr : G.Reachable u v := SimpleGraph.Reachable.of_dist_ne_zero hne obtain ⟨p, hp⟩ := hr.exists_walk_length_eq_dist rw [hdist] at hp rcases p with _ | ⟨hadj1, _ | ⟨hadj2, _ | ⟨hadj3, _ | _⟩⟩⟩ · simp at hp · simp at hp · simp at hp · rename_i w1 w2 refine ⟨G.adjMatrix ℝ u + G.adjMatrix ℝ v, ?_, ?_, ?_, ?_⟩ · intro w exact simple_graph_adj_row_add_is_binary_of_dist_three G u v hdist w · intro hzero have hw := congr_fun hzero w1 simp only [Pi.add_apply, Pi.zero_apply, SimpleGraph.adjMatrix_apply] at hw rw [if_pos hadj1] at hw split_ifs at hw <;> linarith · exact simple_graph_adj_row_add_mem_range G u v · intro l heq have huv : u ≠ v := by intro h subst h simp at hdist have hw1u : w1 ≠ u := hadj1.ne.symm have hw1v : w1 ≠ v := by intro h subst h have hle := G.dist_le hadj1.toWalk simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil, zero_add] at hle omega have hw2u : w2 ≠ u := by intro h subst h have hle := G.dist_le hadj3.toWalk simp only [SimpleGraph.Walk.length_cons, SimpleGraph.Walk.length_nil, zero_add] at hle omega have hw2v : w2 ≠ v := hadj3.ne have hw1w2 : w1 ≠ w2 := hadj2.ne set x : V → ℝ := Pi.single u 1 + Pi.single v 1 - Pi.single l 1 have hx_ker : x ∈ LinearMap.ker (Matrix.toLin' (G.adjMatrix ℝ)) := by rw [LinearMap.mem_ker, map_sub, map_add] rw [simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single G u, simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single G v, simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single G l] rw [heq, sub_self] have hx_ne : x ≠ 0 := by intro hzero by_cases hlu : l = u · have hv := congr_fun hzero v subst hlu simp [x] at hv · have hu := congr_fun hzero u simp [x, hlu, huv] at hu have hnut_nz := hnut.2 x hx_ker hx_ne by_cases hlw1 : l = w1 · have hkw2 : x w2 = 0 := by have : w2 ≠ l := by subst hlw1; exact hw1w2.symm simp [x, hw2u, hw2v, this] exact hnut_nz w2 hkw2 · have hkw1 : x w1 = 0 := by simp [x, hw1u, hw1v, hlw1] exact hnut_nz w1 hkw1 · simp at hp