simple_graph_adj_row_add_is_binary_of_dist_three
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
- simple_graph_disjoint_neighbors_of_dist_threeIn any simple graph, two vertices at distance 3 share no common neighbors.
- Used by 1
- simple_graph_nut_graph_diameter_three_has_binary_vectorLet G be a finite simple nut graph on a finite vertex set. If the diameter of G is 3, then there exists a non-zero (0,1)-vector in the row…
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.
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$.
uses
simple_graph_disjoint_neighbors_of_dist_threehave hdisj := simple_graph_disjoint_neighbors_of_dist_three G u v hdist wThe 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.
uses
Pi.add_apply,SimpleGraph.adjMatrix_applysimp only [Pi.add_apply, SimpleGraph.adjMatrix_apply]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.
by_cases hu : G.Adj u w · have hv : ¬ G.Adj v w := fun h => hdisj ⟨hu, h⟩ simp [hu, hv]
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.
· 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
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.
/-- 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]