AFTD Auto-Formalizing Theoretical Domains

simple_graph_nut_graph_binary_vector_of_triangle_free_edge

theoremverified

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.

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

    lines 10–11

      classical
      refine ⟨fun w => G.adjMatrix ℝ w u + G.adjMatrix ℝ w v, ?_, ?_, ?_, ?_⟩
  2. $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.

    lines 12–21

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

    lines 22–27

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

    lines 28–32

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

    lines 33–44

    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]
  6. $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$.

    lines 45–58

    uses G.ne_of_adj, Pi.sub_apply, Pi.add_apply, Pi.single_eq_same, Pi.single_eq_of_ne, Ne.symm

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

    lines 59–74

    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_ne

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

    lines 75–76

        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

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