corona_k1_exists_maximal_geodesic
For every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, there exist vertices x, y : V ⊕ V and a walk p between them in corona_k1 G such that is_maximal_geodesic p.
Statement
theorem corona_k1_exists_maximal_geodesic {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) : ∃ (x y : V ⊕ V) (p : (corona_k1 G).Walk x y), is_maximal_geodesic p
- Source
- step towards edge_geodesic_transversal_number_corona_k1_card_two
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- 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…
- is_maximal_geodesicA geodesic p from u to v is maximal if no adjacent vertex at either endpoint extends it to a strictly longer geodesic.
- corona_k1_maximal_geodesic_endpointsFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, if p is a walk between x and y in corona_k1 G…
- Arena.Reachable.transReachability is transitive.
- Used by 1
- edge_geodesic_transversal_number_corona_k1_card_twoFor every finite type V with Fintype.card V = 2 and every connected simple graph G on V, the edge geodesic transversal number of the…
The proof, explained
Since |V| ≥ 2 and G is connected, there exist two distinct vertices u, v ∈ V connected by a walk in G. In the corona product corona_k1 G, this gives a walk between the pendant vertices Sum.inr u and Sum.inr v, from which we obtain a shortest path (geodesic) p. Because each pendant vertex Sum.inr x is adjacent only to its base vertex Sum.inl x, any walk leaving Sum.inr u towards a different vertex must first step to Sum.inl u, forcing p to have length strictly greater than dist(Sum.inl u, Sum.inr v). This strict inequality, along with its symmetric counterpart at Sum.inr v, guarantees that the geodesic cannot be extended from either endpoint, making p a maximal geodesic.
There exist distinct vertices u, v ∈ V such that v is reachable from u in G.
Because V has cardinality at least 2, there exist two distinct vertices u, v ∈ V by Fintype.one_lt_card_iff.mp. Since G is connected, u and v are connected by a walk in G.
uses
Fintype.one_lt_card_iff.mpobtain ⟨u, v, huv⟩ := Fintype.one_lt_card_iff.mp hn have h_reach_G : G.Reachable u v := hG u v
The pendant vertices Sum.inr u and Sum.inr v are reachable from each other in corona_k1 G.
By definition of the corona product corona_k1 G, the pendant vertex Sum.inr u is adjacent to Sum.inl u, and Sum.inl v is adjacent to Sum.inr v. The reachability of u and v in G lifts to reachability between Sum.inl u and Sum.inl v via the canonical inclusion homomorphism Sum.inl (using SimpleGraph.Reachable.map). Concatenating these three segments gives a walk from Sum.inr u to Sum.inr v.
uses
SimpleGraph.Reachable.maphave 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 exists a geodesic path p from Sum.inr u to Sum.inr v, reducing the theorem to verifying the neighbor conditions at both endpoints.
Reachability guarantees the existence of a walk p whose length equals the graph distance between Sum.inr u and Sum.inr v. Any walk achieving this minimal length is necessarily a simple path (SimpleGraph.Walk.isPath_of_length_eq_dist). Unfolding the definition of is_maximal_geodesic, p already satisfies the geodesic path condition, leaving two goals: showing that every neighbor of Sum.inr u is within distance p.length from Sum.inr v, and symmetrically for Sum.inr v.
uses
SimpleGraph.Walk.isPath_of_length_eq_distobtain ⟨p, hp_len⟩ := h_reach.exists_walk_length_eq_dist have hp_path : p.IsPath := SimpleGraph.Walk.isPath_of_length_eq_dist p hp_len refine ⟨Sum.inr u, Sum.inr v, p, ?_⟩ dsimp [is_maximal_geodesic] refine ⟨⟨hp_path, hp_len⟩, ?_, ?_⟩
Every neighbor of Sum.inr u is at distance at most p.length from Sum.inr v.
Let w be a neighbor of Sum.inr u. Because pendant vertices in corona_k1 G have degree 1, w must be Sum.inl u by corona_k1_maximal_geodesic_endpoints_adj_inr_inv. Since u ≠ v, the endpoint Sum.inr v is distinct from Sum.inr u. Applying corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le shows that any walk from Sum.inr u to Sum.inr v must pass through Sum.inl u, giving dist(Sum.inl u, Sum.inr v) + 1 ≤ p.length. This inequality immediately implies dist(w, Sum.inr v) ≤ p.length, which is discharged by linear arithmetic (omega).
uses
corona_k1_maximal_geodesic_endpoints_adj_inr_inv,corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le· intro w hw have hw' : (corona_k1 G).Adj (Sum.inr u) w := hw.symm have hw_eq : w = Sum.inl u := corona_k1_maximal_geodesic_endpoints_adj_inr_inv G u hw' subst hw_eq have hy_ne : (Sum.inr v : V ⊕ V) ≠ Sum.inr u := by intro h injection h with h' exact huv.symm h' have h_le := corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le G u (Sum.inr v) p hy_ne omega
Every neighbor of Sum.inr v is at distance at most p.length from Sum.inr u.
Symmetrically, any neighbor w of Sum.inr v must be Sum.inl v (corona_k1_maximal_geodesic_endpoints_adj_inr_inv). Since Sum.inr u ≠ Sum.inr v, applying corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le to the reversed walk p.reverse yields dist(Sum.inl v, Sum.inr u) + 1 ≤ p.reverse.length. Using symmetry of distance (SimpleGraph.dist_comm) and invariance of length under reversal (SimpleGraph.Walk.length_reverse), linear arithmetic (omega) concludes that dist(Sum.inr u, w) ≤ p.length.
uses
corona_k1_maximal_geodesic_endpoints_adj_inr_inv,corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le,SimpleGraph.dist_comm,SimpleGraph.Walk.length_reverse· intro w hw have hw_eq : w = Sum.inl v := corona_k1_maximal_geodesic_endpoints_adj_inr_inv G v hw subst hw_eq have hy_ne : (Sum.inr u : V ⊕ V) ≠ Sum.inr v := by intro h injection h with h' exact huv h' have h_le := corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le G v (Sum.inr u) p.reverse hy_ne rw [SimpleGraph.dist_comm] rw [SimpleGraph.Walk.length_reverse] at h_le omega
Fintype.one_lt_card_iff.mp- A finite type has cardinality at least 2 (greater than 1) if and only if it contains at least two distinct elements.
SimpleGraph.Reachable.map- A graph homomorphism maps reachable pairs of vertices to reachable pairs of vertices.
SimpleGraph.Walk.isPath_of_length_eq_dist- A walk whose length equals the graph distance between its endpoints is a simple path.
corona_k1_maximal_geodesic_endpoints_adj_inr_inv- In the corona product of a graph with K₁, the only neighbor of a pendant vertex Sum.inr u is its corresponding base vertex Sum.inl u.
corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le- Any walk in the corona product from a pendant vertex Sum.inr u to a distinct vertex y has length at least dist(Sum.inl u, y) + 1.
SimpleGraph.dist_comm- Graph distance is symmetric: dist(u, v) = dist(v, u).
SimpleGraph.Walk.length_reverse- Reversing a walk preserves its length.
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.
/-- For every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, there exist vertices x, y in the corona product corona_k1 G and a walk between them that is a maximal geodesic. -/theorem corona_k1_exists_maximal_geodesic {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) : ∃ (x y : V ⊕ V) (p : (corona_k1 G).Walk x y), is_maximal_geodesic p := by obtain ⟨u, v, huv⟩ := Fintype.one_lt_card_iff.mp hn 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 obtain ⟨p, hp_len⟩ := h_reach.exists_walk_length_eq_dist have hp_path : p.IsPath := SimpleGraph.Walk.isPath_of_length_eq_dist p hp_len refine ⟨Sum.inr u, Sum.inr v, p, ?_⟩ dsimp [is_maximal_geodesic] refine ⟨⟨hp_path, hp_len⟩, ?_, ?_⟩ · intro w hw have hw' : (corona_k1 G).Adj (Sum.inr u) w := hw.symm have hw_eq : w = Sum.inl u := corona_k1_maximal_geodesic_endpoints_adj_inr_inv G u hw' subst hw_eq have hy_ne : (Sum.inr v : V ⊕ V) ≠ Sum.inr u := by intro h injection h with h' exact huv.symm h' have h_le := corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le G u (Sum.inr v) p hy_ne omega · intro w hw have hw_eq : w = Sum.inl v := corona_k1_maximal_geodesic_endpoints_adj_inr_inv G v hw subst hw_eq have hy_ne : (Sum.inr u : V ⊕ V) ≠ Sum.inr v := by intro h injection h with h' exact huv h' have h_le := corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le G v (Sum.inr u) p.reverse hy_ne rw [SimpleGraph.dist_comm] rw [SimpleGraph.Walk.length_reverse] at h_le omega