simple_graph_ones_mem_range_imp_has_binary_vector
For 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 ℝ), then 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_ones_mem_range_imp_has_binary_vector {V : Type*} [Fintype V] [Nonempty V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (h1 : (fun _ : V => (1 : ℝ)) ∈ LinearMap.range (Matrix.toLin' (G.adjMatrix ℝ))) : ∃ 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- Used by 1
- simple_graph_regular_has_binary_vectorFor 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…
Read back from the Lean
Let V be a finite, nonempty type with decidable equality, and let G be a simple graph on V with decidable adjacency.
Assume hypothesis h1: the all-ones vector on V (the function mapping every vertex to (1 : ℝ)) belongs to the range of the linear map defined by the adjacency matrix of G over ℝ (i.e., the column space / image of G.adjMatrix ℝ).
Then, there exists a vector y : V → ℝ such that:
1. Every component of y is 0 or 1 (∀ v : V, y v = 0 ∨ y v = 1),
2. y is not the zero vector (y ≠ 0),
3. y is in the range of the linear map defined by G.adjMatrix ℝ, and
4. y is not equal to any row of the adjacency matrix of G (∀ u : V, y ≠ 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 chooses the constant all-ones vector as the desired witness. By assumption, the all-ones vector is in the row space of the adjacency matrix, and every component is 1 ∈ {0, 1}. Because the vertex set is non-empty, evaluating the vector at an arbitrary vertex shows it is non-zero. Finally, since simple graphs contain no self-loops, every diagonal entry of the adjacency matrix is 0, so the all-ones vector cannot equal any row of the matrix.
The all-ones vector is chosen as the witness, satisfying the binary coordinate requirement and lying in the adjacency row space.
We instantiate the existential quantifier with the constant all-ones vector. Every coordinate is 1, so each entry trivially belongs to {0, 1}. The assumption that the all-ones vector is in the range of the adjacency matrix directly satisfies the submodule membership condition, reducing the theorem to showing that this vector is non-zero and differs from every row of the adjacency matrix.
uses
Or.inrrefine ⟨fun _ => 1, fun v => Or.inr rfl, ?_, h1, ?_⟩
The all-ones vector is non-zero.
Suppose for contradiction that the all-ones vector is the zero vector. Because the vertex set V is non-empty, we can pick an arbitrary vertex. Evaluating both sides of the assumed equation at that vertex gives 1 = 0, a contradiction.
uses
congrFun,Classical.arbitrary· intro h have := congrFun h (Classical.arbitrary V) simp at this
The all-ones vector does not equal any row of the adjacency matrix.
Fix any vertex u and assume for contradiction that the all-ones vector equals the u-th row of the adjacency matrix. Evaluating both functions at u equates the left-hand value, 1, with the diagonal matrix entry at (u, u). Since simple graphs have no self-loops, this diagonal entry is 0, yielding 1 = 0, which is impossible.
uses
congrFun,SimpleGraph.adjMatrix_apply· intro u h have := congrFun h u simp [SimpleGraph.adjMatrix_apply] at this
Or.inr- If a proposition b holds, then the disjunction a ∨ b holds.
congrFun- If two functions are equal, then their values at any input are equal.
Classical.arbitrary- Chooses an unspecified element from any non-empty type.
SimpleGraph.adjMatrix_apply- The (v, w)-entry of the adjacency matrix of a simple graph is 1 if v is adjacent to w, and 0 otherwise.
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 the all-ones vector is in the adjacency row space of a nonempty finite simple graph, it is a non-zero (0,1)-vector not occurring as a row. -/theorem simple_graph_ones_mem_range_imp_has_binary_vector {V : Type*} [Fintype V] [Nonempty V] [DecidableEq V] (G : SimpleGraph V) [DecidableRel G.Adj] (h1 : (fun _ : V => (1 : ℝ)) ∈ LinearMap.range (Matrix.toLin' (G.adjMatrix ℝ))) : ∃ 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 refine ⟨fun _ => 1, fun v => Or.inr rfl, ?_, h1, ?_⟩ · intro h have := congrFun h (Classical.arbitrary V) simp at this · intro u h have := congrFun h u simp [SimpleGraph.adjMatrix_apply] at this