AFTD Auto-Formalizing Theoretical Domains

unreachable_neighbors_of_no_cycle

lemmaverified

If a vertex v in a simple graph G does not lie on any cycle from v to v, then any two distinct neighbors u and w of v are not reachable from each other in the induced subgraph G - v obtained by deleting v.

Statement

lemma unreachable_neighbors_of_no_cycle {V : Type*} (G : SimpleGraph V) (v : V)
    (hno : ¬ ∃ (p : G.Walk v v), p.IsCycle) (u w : V) (hu : G.Adj v u) (hw : G.Adj v w) (hne : u ≠ w) :
    ¬ (G.induce ({v}ᶜ : Set V)).Reachable ⟨u, (G.ne_of_adj hu).symm⟩ ⟨w, (G.ne_of_adj hw).symm⟩
Source
arXiv:2610.26912: Theorem 2.22 -- Vertex Removal and Vertex-Edge Domination
Verified
21 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cycle_of_reachable_neighborsIf two distinct neighbors u and w of a vertex v in a simple graph G are reachable from each other in the induced subgraph G - v obtained…

Read back from the Lean

Let $V$ be a type, $G$ be a simple graph on $V$, and $v \in V$ be a vertex. Assume that there is no walk from $v$ to $v$ in $G$ that is a cycle. Then, for any vertices $u, w \in V$ such that $v$ is adjacent to $u$, $v$ is adjacent to $w$, and $u \neq w$, the vertices $u$ and $w$ are not reachable from each other in the induced subgraph of $G$ on $V \setminus \{v\}$ (the complement of $\{v\}$).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- If v lies on no cycle, its distinct neighbors belong to different components of G - v. -/
lemma unreachable_neighbors_of_no_cycle {V : Type*} (G : SimpleGraph V) (v : V)
    (hno : ¬ ∃ (p : G.Walk v v), p.IsCycle) (u w : V) (hu : G.Adj v u) (hw : G.Adj v w) (hne : u ≠ w) :
    ¬ (G.induce ({v}ᶜ : Set V)).Reachable ⟨u, (G.ne_of_adj hu).symm⟩ ⟨w, (G.ne_of_adj hw).symm⟩ := fun hreach => hno (cycle_of_reachable_neighbors G v u w hu hw hne hreach)
See it in the graphDiscuss this resultChallenge it