simple_graph_nut_graph_binary_vector_of_triangle_free_edge
If a finite simple nut graph with at least 4 vertices has a triangle-free edge (an edge whose endpoints share no common neighbors), then the sum of the rows of its endpoints is a non-row (0,1)-vector in the row space of the adjacency matrix.
Statement
theorem simple_graph_nut_graph_binary_vector_of_triangle_free_edge {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) (hadj : G.Adj u v) (htri : ∀ w : V, ¬(G.Adj u w ∧ G.Adj v w)) : ∃ 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
- Source
- step towards op_1267_diameter_two_nut_graph_has_binary_vector
- Verified
- 12 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…
The proof, explained
The proof considers the candidate vector $y = \text{col}_u(A) + \text{col}_v(A)$, the sum of the columns of the adjacency matrix corresponding to the endpoints of the triangle-free edge $(u, v)$. Because $(u, v)$ is triangle-free, no vertex is adjacent to both $u$ and $v$, which makes $y$ a non-zero $(0,1)$-vector belonging to the column space via the preimage $e_u + e_v$. If $y$ were equal to any row $l$ of $A$, the vector $z = e_u + e_v - e_l$ would be a non-zero kernel vector supported on at most three vertices. Since the graph has at least four vertices, $z$ must vanish at some vertex, directly contradicting the nut graph property that every non-zero null vector has nowhere-vanishing entries.
Consider the candidate vector $y$ whose entry at each vertex $w$ is $A_{w, u} + A_{w, v}$, the sum of the columns corresponding to $u$ and $v$.
To prove the existential claim, we instantiate the witness $y$ as the sum of the columns of the adjacency matrix $A$ associated with the endpoints $u$ and $v$ of the edge, leaving four subgoals to verify.
classical refine ⟨fun w => G.adjMatrix ℝ w u + G.adjMatrix ℝ w v, ?_, ?_, ?_, ?_⟩
$y$ is a $(0, 1)$-vector: for every vertex $w$, $y(w) = 0$ or $y(w) = 1$.
The entry $y(w) = A_{w, u} + A_{w, v}$ is the sum of the indicators of whether $w$ is adjacent to $u$ and whether $w$ is adjacent to $v$. By assumption, the edge $(u, v)$ is triangle-free, so no vertex $w$ can be adjacent to both $u$ and $v$. A case split on adjacency to $u$ and $v$ shows that $y(w) = 1$ if $w$ is adjacent to exactly one endpoint, and $y(w) = 0$ if adjacent to neither.
uses
SimpleGraph.adjMatrix_apply,G.adj_comm· -- y is a (0,1)-vector, since no vertex is adjacent to both u and v intro w simp only [SimpleGraph.adjMatrix_apply] by_cases h1 : G.Adj w u · by_cases h2 : G.Adj w v · exact absurd ⟨(G.adj_comm w u).1 h1, (G.adj_comm w v).1 h2⟩ (htri w) · right; simp [h1, h2] · by_cases h2 : G.Adj w v · right; simp [h1, h2] · left; simp [h1, h2]
$y \neq 0$.
Suppose for contradiction that $y = 0$. Then $y(v) = 0$. But $y(v) = A_{v, u} + A_{v, v} = 1 + 0 = 1$, since $u$ and $v$ are adjacent and simple graphs have no self-loops ($A_{v, v} = 0$). This forces $1 = 0$, a contradiction.
uses
SimpleGraph.adjMatrix_apply,SimpleGraph.irrefl,if_false,add_zero,if_pos,G.adj_comm,one_ne_zero· -- y ≠ 0, since y v = 1 intro h have hv : (fun w => G.adjMatrix ℝ w u + G.adjMatrix ℝ w v) v = 0 := by rw [h]; rfl simp only [SimpleGraph.adjMatrix_apply, SimpleGraph.irrefl G, if_false, add_zero, if_pos ((G.adj_comm v u).2 hadj)] at hv exact one_ne_zero hv
$y$ belongs to the range of the linear map defined by the adjacency matrix $A$.
We provide the preimage $x = e_u + e_v$, the sum of the standard basis vectors for $u$ and $v$. Applying $A$ gives $A(e_u + e_v) = A e_u + A e_v = \text{col}_u(A) + \text{col}_v(A)$, which is precisely $y$.
uses
LinearMap.mem_range.2,Matrix.toLin'_apply,Matrix.mulVec_add,Matrix.mulVec_single_one,Matrix.col_apply· -- y is the image of the (0,1)-vector e_u + e_v refine LinearMap.mem_range.2 ⟨Pi.single u 1 + Pi.single v 1, ?_⟩ rw [Matrix.toLin'_apply, Matrix.mulVec_add, Matrix.mulVec_single_one, Matrix.mulVec_single_one] funext w simp [Matrix.col_apply]
If $y$ were equal to the $l$-th row of $A$ for some vertex $l$, then $z = e_u + e_v - e_l$ would lie in the kernel of $A$.
Assume $y = A l$. The adjacency matrix of a simple graph is symmetric ($A_{a, b} = A_{b, a}$). Under matrix multiplication, $A z = A(e_u + e_v - e_l) = \text{col}_u(A) + \text{col}_v(A) - \text{col}_l(A)$. For each vertex $w$, this component equals $(A_{w, u} + A_{w, v}) - A_{w, l} = y(w) - A_{l, w} = A_{l, w} - A_{l, w} = 0$. Hence $A z = 0$, so $z \in \ker A$.
uses
SimpleGraph.adjMatrix_apply,G.adj_comm,LinearMap.mem_ker,Matrix.toLin'_apply,Matrix.mulVec_sub,Matrix.mulVec_add,Matrix.mulVec_single_one,Pi.sub_apply,Pi.add_apply,Matrix.col_apply,Pi.zero_apply,congrFun,sub_self· -- y is not a row: otherwise e_u + e_v - e_l would be a sparse null vector intro l hy have hsym : ∀ a b : V, G.adjMatrix ℝ a b = G.adjMatrix ℝ b a := by intro a b; simp [SimpleGraph.adjMatrix_apply, G.adj_comm] set z : V → ℝ := Pi.single u 1 + Pi.single v 1 - Pi.single l 1 with hzdef have hker : z ∈ (Matrix.toLin' (G.adjMatrix ℝ)).ker := by rw [LinearMap.mem_ker, Matrix.toLin'_apply, hzdef, Matrix.mulVec_sub, Matrix.mulVec_add, Matrix.mulVec_single_one, Matrix.mulVec_single_one, Matrix.mulVec_single_one] funext w simp only [Pi.sub_apply, Pi.add_apply, Matrix.col_apply, Pi.zero_apply] have hyw : G.adjMatrix ℝ w u + G.adjMatrix ℝ w v = G.adjMatrix ℝ l w := congrFun hy w rw [hyw, hsym l w, sub_self]
$z \neq 0$.
Since $u$ and $v$ are adjacent, they are distinct ($u \neq v$). If $z = 0$, then $z(v) = 0$ and $z(u) = 0$. If $l = u$, then $z(v) = e_v(v) = 1 \neq 0$. If $l \neq u$, then $z(u) = e_u(u) = 1 \neq 0$. In either case we obtain a contradiction, showing $z \neq 0$.
uses
G.ne_of_adj,Pi.sub_apply,Pi.add_apply,Pi.single_eq_same,Pi.single_eq_of_ne,Ne.symmhave huv : u ≠ v := G.ne_of_adj hadj have hzne : z ≠ 0 := by intro hz0 have hzv : z v = 0 := by rw [hz0]; rfl have hzu : z u = 0 := by rw [hz0]; rfl by_cases hlu : l = u · rw [hzdef] at hzv simp only [Pi.sub_apply, Pi.add_apply] at hzv rw [Pi.single_eq_same, Pi.single_eq_of_ne huv.symm, hlu, Pi.single_eq_of_ne huv.symm] at hzv norm_num at hzv · rw [hzdef] at hzu simp only [Pi.sub_apply, Pi.add_apply] at hzu rw [Pi.single_eq_same, Pi.single_eq_of_ne huv, Pi.single_eq_of_ne (Ne.symm hlu)] at hzu norm_num at hzu
There exists a vertex $w$ such that $z(w) = 0$.
The support of $z = e_u + e_v - e_l$ is contained in $\{u, v, l\}$, a set of cardinality at most $3$. Because the graph has at least $4$ vertices ($|V| \ge 4$), $\{u, v, l\}$ cannot cover all of $V$, so there exists some vertex $w \notin \{u, v, l\}$. For this vertex, $e_u(w) = e_v(w) = e_l(w) = 0$, so $z(w) = 0$.
uses
Finset.card_univ,Finset.card_insert_le,Finset.card_singleton,Finset.exists_mem_notMem_of_card_lt_card,Finset.mem_insert,Finset.mem_singleton,not_or,Pi.sub_apply,Pi.add_apply,Pi.single_eq_of_nehave hzero : ∃ w : V, z w = 0 := by have hlt : ({u, v, l} : Finset V).card < (Finset.univ : Finset V).card := by rw [Finset.card_univ] have h1 : ({u, v, l} : Finset V) = insert u (insert v {l}) := rfl have a := Finset.card_insert_le u (insert v ({l} : Finset V)) have b := Finset.card_insert_le v ({l} : Finset V) have c : ({l} : Finset V).card = 1 := Finset.card_singleton l omega obtain ⟨w, -, hw⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt refine ⟨w, ?_⟩ simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hw obtain ⟨hwu, hwv, hwl⟩ := hw rw [hzdef] simp only [Pi.sub_apply, Pi.add_apply] rw [Pi.single_eq_of_ne hwu, Pi.single_eq_of_ne hwv, Pi.single_eq_of_ne hwl] norm_num
The existence of $z$ contradicts the nut graph property, concluding that $y$ cannot be a row of $A$.
In a nut graph, every non-zero vector in the kernel of the adjacency matrix must be non-zero at every vertex. But $z$ is a non-zero kernel vector with $z(w) = 0$. This contradiction establishes that $y$ cannot equal any row of $A$.
obtain ⟨w, hw⟩ := hzero exact hnut.2 z hker hzne w hw
add_zero- Adding zero to an element leaves it unchanged ($a + 0 = a$).
congrFun- If two functions are equal, they take equal values at any point.
Finset.card_insert_le- Inserting an element into a finite set increases its cardinality by at most $1$.
Finset.card_singleton- A singleton finite set $\{l\}$ has cardinality $1$.
Finset.card_univ- The cardinality of the finset of all elements of a finite type $V$ equals the cardinality $|V|$ of the type.
Finset.exists_mem_notMem_of_card_lt_card- If a finite set has strictly smaller cardinality than another, there is an element in the larger set not contained in the smaller.
Finset.mem_insert- An element belongs to $\{a\} ∪ s$ if and only if it equals $a$ or belongs to $s$.
Finset.mem_singleton- An element belongs to the singleton $\{a\}$ if and only if it equals $a$.
G.adj_comm- Adjacency in $G$ is symmetric: $u$ is adjacent to $v$ if and only if $v$ is adjacent to $u$.
G.ne_of_adj- Adjacent vertices in a simple graph are distinct.
if_false- An if-then-else expression with a false condition evaluates to its else branch.
if_pos- An if-then-else expression with a true condition evaluates to its then branch.
LinearMap.mem_ker- A vector is in the kernel of a linear map if and only if the map evaluates to zero on it.
LinearMap.mem_range.2- A vector is in the range of a linear map if it is the image of some element.
Matrix.col_apply- The $i$-th entry of column $j$ of matrix $M$ is the matrix entry $M_{i, j}$.
Matrix.mulVec_add- Matrix-vector multiplication distributes over vector addition: $M(x + y) = M x + M y$.
Matrix.mulVec_single_one- Multiplying a matrix $M$ by the standard basis vector $e_j$ yields the $j$-th column of $M$.
Matrix.mulVec_sub- Matrix-vector multiplication distributes over vector subtraction: $M(x - y) = M x - M y$.
Matrix.toLin'_apply- The linear map induced by a matrix $M$ acts on a vector $x$ by matrix-vector multiplication $M x$.
Ne.symm- Inequality is symmetric: if $a ≠ b$ then $b ≠ a$.
not_or- The negation of a disjunction is equivalent to the conjunction of the negations: $\neg(P \lor Q) \leftrightarrow \neg P \land \neg Q$.
one_ne_zero- In a non-trivial semiring (such as $\mathbb{R}$), $1 ≠ 0$.
Pi.add_apply- Pointwise addition of functions: $(f + g)(w) = f(w) + g(w)$.
Pi.single_eq_same- The standard basis vector $e_i$ evaluated at $i$ equals its assigned value.
Pi.single_eq_of_ne- The standard basis vector $e_i$ evaluated at any coordinate $j ≠ i$ equals $0$.
Pi.sub_apply- Pointwise subtraction of functions: $(f - g)(w) = f(w) - g(w)$.
Pi.zero_apply- The zero function evaluates to $0$ everywhere: $0(w) = 0$.
SimpleGraph.adjMatrix_apply- The $(v, w)$ entry of the adjacency matrix is $1$ if $v$ is adjacent to $w$, and $0$ otherwise.
SimpleGraph.irrefl- Adjacency is irreflexive: no vertex is adjacent to itself.
sub_self- Subtracting any element from itself gives zero ($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.
/-- If a finite simple nut graph on at least 4 vertices has a triangle-free edge, then the sum of its endpoint rows is a non-row (0,1)-vector in the row space of the adjacency matrix. -/theorem simple_graph_nut_graph_binary_vector_of_triangle_free_edge {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) (hadj : G.Adj u v) (htri : ∀ w : V, ¬(G.Adj u w ∧ G.Adj v w)) : ∃ 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 classical refine ⟨fun w => G.adjMatrix ℝ w u + G.adjMatrix ℝ w v, ?_, ?_, ?_, ?_⟩ · -- y is a (0,1)-vector, since no vertex is adjacent to both u and v intro w simp only [SimpleGraph.adjMatrix_apply] by_cases h1 : G.Adj w u · by_cases h2 : G.Adj w v · exact absurd ⟨(G.adj_comm w u).1 h1, (G.adj_comm w v).1 h2⟩ (htri w) · right; simp [h1, h2] · by_cases h2 : G.Adj w v · right; simp [h1, h2] · left; simp [h1, h2] · -- y ≠ 0, since y v = 1 intro h have hv : (fun w => G.adjMatrix ℝ w u + G.adjMatrix ℝ w v) v = 0 := by rw [h]; rfl simp only [SimpleGraph.adjMatrix_apply, SimpleGraph.irrefl G, if_false, add_zero, if_pos ((G.adj_comm v u).2 hadj)] at hv exact one_ne_zero hv · -- y is the image of the (0,1)-vector e_u + e_v refine LinearMap.mem_range.2 ⟨Pi.single u 1 + Pi.single v 1, ?_⟩ rw [Matrix.toLin'_apply, Matrix.mulVec_add, Matrix.mulVec_single_one, Matrix.mulVec_single_one] funext w simp [Matrix.col_apply] · -- y is not a row: otherwise e_u + e_v - e_l would be a sparse null vector intro l hy have hsym : ∀ a b : V, G.adjMatrix ℝ a b = G.adjMatrix ℝ b a := by intro a b; simp [SimpleGraph.adjMatrix_apply, G.adj_comm] set z : V → ℝ := Pi.single u 1 + Pi.single v 1 - Pi.single l 1 with hzdef have hker : z ∈ (Matrix.toLin' (G.adjMatrix ℝ)).ker := by rw [LinearMap.mem_ker, Matrix.toLin'_apply, hzdef, Matrix.mulVec_sub, Matrix.mulVec_add, Matrix.mulVec_single_one, Matrix.mulVec_single_one, Matrix.mulVec_single_one] funext w simp only [Pi.sub_apply, Pi.add_apply, Matrix.col_apply, Pi.zero_apply] have hyw : G.adjMatrix ℝ w u + G.adjMatrix ℝ w v = G.adjMatrix ℝ l w := congrFun hy w rw [hyw, hsym l w, sub_self] have huv : u ≠ v := G.ne_of_adj hadj have hzne : z ≠ 0 := by intro hz0 have hzv : z v = 0 := by rw [hz0]; rfl have hzu : z u = 0 := by rw [hz0]; rfl by_cases hlu : l = u · rw [hzdef] at hzv simp only [Pi.sub_apply, Pi.add_apply] at hzv rw [Pi.single_eq_same, Pi.single_eq_of_ne huv.symm, hlu, Pi.single_eq_of_ne huv.symm] at hzv norm_num at hzv · rw [hzdef] at hzu simp only [Pi.sub_apply, Pi.add_apply] at hzu rw [Pi.single_eq_same, Pi.single_eq_of_ne huv, Pi.single_eq_of_ne (Ne.symm hlu)] at hzu norm_num at hzu have hzero : ∃ w : V, z w = 0 := by have hlt : ({u, v, l} : Finset V).card < (Finset.univ : Finset V).card := by rw [Finset.card_univ] have h1 : ({u, v, l} : Finset V) = insert u (insert v {l}) := rfl have a := Finset.card_insert_le u (insert v ({l} : Finset V)) have b := Finset.card_insert_le v ({l} : Finset V) have c : ({l} : Finset V).card = 1 := Finset.card_singleton l omega obtain ⟨w, -, hw⟩ := Finset.exists_mem_notMem_of_card_lt_card hlt refine ⟨w, ?_⟩ simp only [Finset.mem_insert, Finset.mem_singleton, not_or] at hw obtain ⟨hwu, hwv, hwl⟩ := hw rw [hzdef] simp only [Pi.sub_apply, Pi.add_apply] rw [Pi.single_eq_of_ne hwu, Pi.single_eq_of_ne hwv, Pi.single_eq_of_ne hwl] norm_num obtain ⟨w, hw⟩ := hzero exact hnut.2 z hker hzne w hw