AFTD Auto-Formalizing Theoretical Domains

simple_graph_regular_has_binary_vector

theoremverifiedoriginal

For any nonempty finite simple graph G that is regular of degree d with 0 < d, 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_regular_has_binary_vector
    {V : Type*} [Fintype V] [Nonempty V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (d : ℕ) (hd : 0 < d)
    (hreg : G.IsRegularOfDegree d) :
    ∃ 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
Related work
arXiv:2611.08244 Thm 2.5
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

Read back from the Lean

For any finite, nonempty type V with decidable equality, any simple graph G on V with decidable adjacency, and any natural number d such that 0 < d: if G is regular of degree d, then there exists a function y : V → ℝ such that: 1. For all v : V, y v = 0 or y v = 1; 2. y is not the zero function (y ≠ 0); 3. y is in the range of the linear map Matrix.toLin' (G.adjMatrix ℝ) (i.e., in the real column space of the adjacency matrix of G); 4. For all u : V, y is not equal to row u of the adjacency matrix of G (G.adjMatrix ℝ 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 reduces the goal via simple_graph_ones_mem_range_imp_has_binary_vector to showing that the all-ones vector lies in the image of the adjacency matrix. It witnesses this preimage by the constant vector with entry 1/d. By d-regularity, multiplying the adjacency matrix by this constant vector gives d * (1/d) at every vertex, which simplifies to 1 since d > 0.

  1. It suffices to show that the all-ones vector is in the range of the linear map induced by the adjacency matrix of G.

    Applying simple_graph_ones_mem_range_imp_has_binary_vector reduces the existence of the desired non-zero (0,1)-vector to showing that the constant function taking value 1 everywhere lies in the range of Matrix.toLin' (G.adjMatrix ℝ).

    line 9

    uses simple_graph_ones_mem_range_imp_has_binary_vector

      apply simple_graph_ones_mem_range_imp_has_binary_vector
  2. It suffices to show that the linear map of the adjacency matrix maps the constant vector with value 1/d to the all-ones vector.

    To show that the all-ones vector belongs to the range of the linear map, we choose the constant vector with value 1/d as the witness for the preimage.

    line 10

    uses Function.const

      refine ⟨Function.const V ((d : ℝ)⁻¹), ?_⟩
  3. At every vertex v, the adjacency matrix applied to the constant vector 1/d evaluates to d * (1/d).

    We check the function equality pointwise for an arbitrary vertex v. We rewrite the action of the linear map as matrix-vector multiplication using Matrix.toLin'_apply. Then, using SimpleGraph.adjMatrix_mulVec_const_apply_of_regular, the d-regularity of G implies that multiplying the adjacency matrix by the constant vector 1/d evaluates at v to d * (1/d).

    lines 11–14

    uses Matrix.toLin'_apply, SimpleGraph.adjMatrix_mulVec_const_apply_of_regular

      ext v
      rw [Matrix.toLin'_apply]
      rw [SimpleGraph.adjMatrix_mulVec_const_apply_of_regular (α := ℝ) (d := d)
        (a := ((d : ℝ)⁻¹)) hreg]
  4. The product d * (1/d) equals 1, completing the proof that the all-ones vector is in the range.

    Since d is strictly positive, it is non-zero by Nat.pos_iff_ne_zero.mp. Because d ≠ 0 in ℝ, mul_inv_cancel₀ gives d * (1/d) = 1.

    line 15

    uses mul_inv_cancel₀, Nat.pos_iff_ne_zero.mp

      exact mul_inv_cancel₀ (by exact_mod_cast (Nat.pos_iff_ne_zero.mp hd))
simple_graph_ones_mem_range_imp_has_binary_vector
If the all-ones vector is in the range of the linear map of a simple graph's adjacency matrix over ℝ, then there exists a non-zero (0,1)-vector in that range that is not equal to any row of the adjacency matrix.
Function.const
The constant function that returns the given value for every input.
Matrix.toLin'_apply
Applying the linear map induced by a matrix to a vector equals matrix-vector multiplication.
SimpleGraph.adjMatrix_mulVec_const_apply_of_regular
For a d-regular simple graph, multiplying the adjacency matrix by the constant vector with value a evaluates at any vertex to d * a.
mul_inv_cancel₀
In a group with zero (such as ℝ), multiplying any non-zero element by its inverse yields 1.
Nat.pos_iff_ne_zero.mp
A natural number that is strictly positive is non-zero.

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

/-- Every finite regular simple graph with positive degree has a non-zero (0,1)-vector in its adjacency row space that does not occur as a row. -/theorem simple_graph_regular_has_binary_vector    {V : Type*} [Fintype V] [Nonempty V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (d : ℕ) (hd : 0 < d)    (hreg : G.IsRegularOfDegree d) :    ∃ 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  apply simple_graph_ones_mem_range_imp_has_binary_vector  refine ⟨Function.const V ((d : ℝ)⁻¹), ?_⟩  ext v  rw [Matrix.toLin'_apply]  rw [SimpleGraph.adjMatrix_mulVec_const_apply_of_regular (α := ℝ) (d := d)    (a := ((d : ℝ)⁻¹)) hreg]  exact mul_inv_cancel₀ (by exact_mod_cast (Nat.pos_iff_ne_zero.mp hd))
See it in the graphDiscuss this resultChallenge it