AFTD Auto-Formalizing Theoretical Domains

simple_graph_nut_graph_diameter_three_has_binary_vector

theoremverifiedformalization

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

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.

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

    lines 5–9

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

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

    lines 19–27

    uses SimpleGraph.nontrivial_of_diam_ne_zero, SimpleGraph.exists_dist_eq_diam, SimpleGraph.Reachable.of_dist_ne_zero

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

    lines 28–32

      rcases p with _ | ⟨hadj1, _ | ⟨hadj2, _ | ⟨hadj3, _ | _⟩⟩⟩
      · simp at hp
      · simp at hp
      · simp at hp
      · rename_i w1 w2
  4. 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.

    lines 33–35

    uses simple_graph_adj_row_add_is_binary_of_dist_three

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

    lines 36–40

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

    line 41

    uses simple_graph_adj_row_add_mem_range

        · exact simple_graph_adj_row_add_mem_range G u v
  7. Assuming 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.

    lines 42–61

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

    lines 62–68

    uses LinearMap.mem_ker, map_sub, map_add, simple_graph_nut_graph_diameter_three_has_binary_vector_toLin'_adjMatrix_single, sub_self

          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]
  9. 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.

    lines 69–77

    uses congr_fun

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

    lines 78–85

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

    line 86

      · 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

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