AFTD Auto-Formalizing Theoretical Domains

cycle_of_reachable_neighbors

lemmaverified

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