AFTD Auto-Formalizing Theoretical Domains

simple_graph_adj_row_add_is_binary_of_dist_three

theoremverified

For two vertices at distance 3 in a finite simple graph, the sum of their rows in the adjacency matrix over ℝ is a (0,1)-vector.

Statement

theorem simple_graph_adj_row_add_is_binary_of_dist_three
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V)
    (hdist : G.dist u v = 3) (w : V) :
    (G.adjMatrix ℝ u + G.adjMatrix ℝ v) w = 0 ∨
    (G.adjMatrix ℝ u + G.adjMatrix ℝ v) w = 1
Source
arXiv:2611.08244 Theorem 4.1
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

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. For any vertices $u, v \in V$ such that the graph distance between $u$ and $v$ in $G$ is 3, and for any vertex $w \in V$, the sum of the $u$-th and $v$-th rows of the real adjacency matrix of $G$, evaluated at $w$, is equal to 0 or equal to 1.

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

Because vertices $u$ and $v$ are at distance 3, they cannot share any common neighbor, so no vertex $w$ is adjacent to both. Evaluating the sum of their adjacency matrix rows at coordinate $w$ reduces to the sum of two 0-1 indicator values for adjacency to $u$ and $v$. Case analysis on adjacency shows that at most one indicator can be 1, so the sum at $w$ is always either 0 or 1.

  1. No vertex $w$ can be adjacent to both $u$ and $v$.

    Because $u$ and $v$ are at distance 3, `simple_graph_disjoint_neighbors_of_dist_three` implies they cannot share a common neighbor, providing the hypothesis that $u$ and $v$ are not both adjacent to $w$.

    line 8

    uses simple_graph_disjoint_neighbors_of_dist_three

      have hdisj := simple_graph_disjoint_neighbors_of_dist_three G u v hdist w
  2. The entry of the sum vector at $w$ is rewritten as the sum of indicator values: $(\text{if } G.\text{Adj } u\ w \text{ then } 1 \text{ else } 0) + (\text{if } G.\text{Adj } v\ w \text{ then } 1 \text{ else } 0)$.

    Rewriting with `Pi.add_apply` distributes the vector addition to coordinate $w$, and `SimpleGraph.adjMatrix_apply` replaces each adjacency matrix entry with an indicator conditional on adjacency.

    line 9

    uses Pi.add_apply, SimpleGraph.adjMatrix_apply

      simp only [Pi.add_apply, SimpleGraph.adjMatrix_apply]
  3. If $u$ is adjacent to $w$, the sum of the entries at $w$ is 1.

    Assuming $u$ is adjacent to $w$ (`hu`), the disjointness of their neighborhoods implies that $v$ cannot be adjacent to $w$ (`hv`). Substituting these adjacency values into the indicator sum evaluates it to $1 + 0 = 1$, which satisfies the right disjunct.

    lines 10–12

      by_cases hu : G.Adj u w
      · have hv : ¬ G.Adj v w := fun h => hdisj ⟨hu, h⟩
        simp [hu, hv]
  4. If $u$ is not adjacent to $w$, the sum of the entries at $w$ is either 1 or 0.

    Assuming $u$ is not adjacent to $w$ (`hu`), we branch on whether $v$ is adjacent to $w$. If $v$ is adjacent to $w$, the indicator sum simplifies to $0 + 1 = 1$. If $v$ is not adjacent to $w$, it simplifies to $0 + 0 = 0$. In both subcases, the sum is either 0 or 1.

    lines 13–15

      · by_cases hv : G.Adj v w
        · simp [hu, hv]
        · simp [hu, hv]
simple_graph_disjoint_neighbors_of_dist_three
In a simple graph, two vertices at distance 3 share no common neighbors.
Pi.add_apply
The pointwise sum of two functions evaluated at an argument is the sum of their values: $(f + g)(x) = f(x) + g(x)$.
SimpleGraph.adjMatrix_apply
The entry at row $u$ and column $w$ of the adjacency matrix is 1 if $u$ and $w$ are adjacent, 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

/-- The sum of adjacency matrix rows of two vertices at distance 3 is a (0,1)-vector. -/theorem simple_graph_adj_row_add_is_binary_of_dist_three    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] (u v : V)    (hdist : G.dist u v = 3) (w : V) :    (G.adjMatrix ℝ u + G.adjMatrix ℝ v) w = 0 ∨    (G.adjMatrix ℝ u + G.adjMatrix ℝ v) w = 1 := by  have hdisj := simple_graph_disjoint_neighbors_of_dist_three G u v hdist w  simp only [Pi.add_apply, SimpleGraph.adjMatrix_apply]  by_cases hu : G.Adj u w  · have hv : ¬ G.Adj v w := fun h => hdisj ⟨hu, h⟩    simp [hu, hv]  · by_cases hv : G.Adj v w    · simp [hu, hv]    · simp [hu, hv]
See it in the graphDiscuss this resultChallenge it