simple_graph_regular_has_binary_vector
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
- simple_graph_ones_mem_range_imp_has_binary_vectorFor any nonempty finite simple graph G on vertex set V, if the all-ones vector fun _ => 1 is in the range of Matrix.toLin' (G.adjMatrix…
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.
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 ℝ).
uses
simple_graph_ones_mem_range_imp_has_binary_vectorapply simple_graph_ones_mem_range_imp_has_binary_vectorIt 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.
uses
Function.constrefine ⟨Function.const V ((d : ℝ)⁻¹), ?_⟩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).
uses
Matrix.toLin'_apply,SimpleGraph.adjMatrix_mulVec_const_apply_of_regularext v rw [Matrix.toLin'_apply] rw [SimpleGraph.adjMatrix_mulVec_const_apply_of_regular (α := ℝ) (d := d) (a := ((d : ℝ)⁻¹)) hreg]
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.
uses
mul_inv_cancel₀,Nat.pos_iff_ne_zero.mpexact 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
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.
/-- 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))