corona_k1_exists_geodesic_between_leaves
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.
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.
uses
SimpleGraph.Reachable.maphave 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
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.
uses
exists_path_of_distexact 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
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.
/-- 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