AFTD Auto-Formalizing Theoretical Domains

simple_graph_ones_mem_range_imp_has_binary_vector

theoremverifiedoriginal

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

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.

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

    line 9

    uses Or.inr

      refine ⟨fun _ => 1, fun v => Or.inr rfl, ?_, h1, ?_⟩
  2. 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.

    lines 10–12

    uses congrFun, Classical.arbitrary

      · intro h
        have := congrFun h (Classical.arbitrary V)
        simp at this
  3. 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.

    lines 13–15

    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

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