cycle_of_reachable_neighbors
If 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 by deleting v, then there exists a cycle in G from v to v.
Statement
lemma cycle_of_reachable_neighbors {V : Type*} (G : SimpleGraph V) (v u w : V) (huv : G.Adj v u) (hvw : G.Adj v w) (hne : u ≠ w) (hreach : (G.induce ({v}ᶜ : Set V)).Reachable ⟨u, (G.ne_of_adj huv).symm⟩ ⟨w, (G.ne_of_adj hvw).symm⟩) : ∃ (p : G.Walk v v), p.IsCycle
- Source
- arXiv:2610.26912: Theorem 2.22 -- Vertex Removal and Vertex-Edge Domination
- Verified
- 21 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- unreachable_neighbors_of_no_cycleIf 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…
Read back from the Lean
Let $V$ be a type, $G$ be a simple graph on $V$, and $v, u, w \in V$ be vertices.
Assume:
1. $v$ is adjacent to $u$ in $G$ (G.Adj v u),
2. $v$ is adjacent to $w$ in $G$ (G.Adj v w),
3. $u \neq w$, and
4. in the induced subgraph $G[V \setminus \{v\}]$ (the subgraph induced by the complement of $\{v\}$), the vertex $u$ is reachable from $w$ (i.e., there is a walk between them in the induced subgraph).
Then there exists a walk $p$ in $G$ from $v$ to $v$ such that $p$ is a cycle (p.IsCycle).
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
/-- Two distinct neighbors of v reachable in G - v determine a cycle containing v. -/ lemma cycle_of_reachable_neighbors {V : Type*} (G : SimpleGraph V) (v u w : V) (huv : G.Adj v u) (hvw : G.Adj v w) (hne : u ≠ w) (hreach : (G.induce ({v}ᶜ : Set V)).Reachable ⟨u, (G.ne_of_adj huv).symm⟩ ⟨w, (G.ne_of_adj hvw).symm⟩) : ∃ (p : G.Walk v v), p.IsCycle := by obtain ⟨q, hq⟩ := SimpleGraph.Reachable.exists_isPath hreach let f : G.induce ({v}ᶜ : Set V) ↪g G := SimpleGraph.Embedding.induce ({v}ᶜ : Set V) let p₁ : G.Walk u w := q.map f.toHom have hq_map : p₁.IsPath := (SimpleGraph.Walk.isPath_map_iff_of_injective f.injective).mpr hq have hv : v ∉ p₁.support := by intro h have h' : v ∈ (q.map f.toHom).support := h rw [SimpleGraph.Walk.support_map, List.mem_map] at h' rcases h' with ⟨x, _, hx⟩ exact x.2 hx let p₂ : G.Walk u v := p₁.concat hvw.symm have hp₂ : p₂.IsPath := by rw [SimpleGraph.Walk.concat_isPath_iff] exact ⟨hq_map, hv⟩ have he : s(v, u) ∉ p₂.edges := by rw [SimpleGraph.Walk.edges_concat] intro he' rw [List.concat_eq_append, List.mem_append, List.mem_singleton] at he' rcases he' with he1 | he2 · have := SimpleGraph.Walk.fst_mem_support_of_mem_edges p₁ he1 exact hv this · rw [Sym2.eq_iff] at he2 rcases he2 with ⟨h1, h2⟩ | ⟨-, h2⟩ · exact (G.ne_of_adj huv) h2.symm · exact hne h2 refine ⟨SimpleGraph.Walk.cons huv p₂, ?_⟩ rw [SimpleGraph.Walk.cons_isCycle_iff] exact ⟨hp₂, he⟩