AFTD Auto-Formalizing Theoretical Domains

corona_k1_exists_geodesic_between_leaves

theoremverified

For every finite type V and every connected simple graph G on V, between any two leaves Sum.inr u and Sum.inr v in corona_k1 G, there exists a walk that is a path and has length equal to the distance between them.

Statement

theorem corona_k1_exists_geodesic_between_leaves
    {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (u v : V) :
    ∃ p : (corona_k1 G).Walk (Sum.inr u) (Sum.inr v),
      p.IsPath ∧ p.length = (corona_k1 G).dist (Sum.inr u) (Sum.inr v)
Source
step towards edge_geodesic_transversal_number_corona_k1
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • corona_k1The corona product G ⊙ K_1 of a graph G with K_1 is the graph on vertex set V ⊕ V where the first copy induces G, each vertex in the…
  • Arena.Reachable.transReachability is transitive.

The proof, explained

To find a geodesic path between two leaves Sum.inr u and Sum.inr v in the corona product corona_k1 G, the proof first establishes that they are reachable from each other. Reachability follows by stepping from the leaf Sum.inr u to the base vertex Sum.inl u, following the embedded walk in G from Sum.inl u to Sum.inl v (using connectivity of G), and stepping to the leaf Sum.inr v. The theorem then follows from the general fact that any reachable pair of vertices is joined by a path of minimal distance.

  1. The leaf vertices Sum.inr u and Sum.inr v are reachable from each other in corona_k1 G.

    Since G is connected, there is a walk between u and v in G. In the corona product corona_k1 G, the leaf Sum.inr u is by definition adjacent to the corresponding base vertex Sum.inl u, and Sum.inl v is adjacent to Sum.inr v. Furthermore, the canonical inclusion Sum.inl is a graph homomorphism from G to corona_k1 G, so mapping the walk in G yields a walk from Sum.inl u to Sum.inl v. Composing these three segments shows that Sum.inr u can reach Sum.inr v.

    lines 6–12

    uses SimpleGraph.Reachable.map

      have h_reach_G : G.Reachable u v := hG u v
      have h1 : (corona_k1 G).Adj (Sum.inr u) (Sum.inl u) := rfl
      have h2 : (corona_k1 G).Reachable (Sum.inl u) (Sum.inl v) :=
        SimpleGraph.Reachable.map ⟨Sum.inl, fun h => h⟩ h_reach_G
      have h3 : (corona_k1 G).Adj (Sum.inl v) (Sum.inr v) := rfl
      have h_reach : (corona_k1 G).Reachable (Sum.inr u) (Sum.inr v) :=
        (h1.reachable.trans h2).trans h3.reachable
  2. There is a path from Sum.inr u to Sum.inr v whose length equals the graph distance between them.

    Whenever two vertices in a graph are reachable from each other, there exists a path connecting them whose length achieves the graph distance.

    line 13

    uses exists_path_of_dist

      exact h_reach.exists_path_of_dist
SimpleGraph.Reachable.map
A graph homomorphism maps reachable vertices to reachable vertices.
exists_path_of_dist
If two vertices in a graph are reachable from one another, there is a path connecting them whose length equals the graph distance between them.

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

/-- Between any two leaves in the corona product corona_k1 G of a connected graph, there exists a path that is a geodesic. -/theorem corona_k1_exists_geodesic_between_leaves    {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (u v : V) :    ∃ p : (corona_k1 G).Walk (Sum.inr u) (Sum.inr v),      p.IsPath ∧ p.length = (corona_k1 G).dist (Sum.inr u) (Sum.inr v) := by  have h_reach_G : G.Reachable u v := hG u v  have h1 : (corona_k1 G).Adj (Sum.inr u) (Sum.inl u) := rfl  have h2 : (corona_k1 G).Reachable (Sum.inl u) (Sum.inl v) :=    SimpleGraph.Reachable.map ⟨Sum.inl, fun h => h⟩ h_reach_G  have h3 : (corona_k1 G).Adj (Sum.inl v) (Sum.inr v) := rfl  have h_reach : (corona_k1 G).Reachable (Sum.inr u) (Sum.inr v) :=    (h1.reachable.trans h2).trans h3.reachable  exact h_reach.exists_path_of_dist
See it in the graphDiscuss this resultChallenge it