corona_k1_maximal_geodesic_endpoints
For 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 such that is_maximal_geodesic p, then there exist u v : V such that x = Sum.inr u ∧ y = Sum.inr v ∧ u ≠ v.
Statement
theorem corona_k1_maximal_geodesic_endpoints {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) (hp : is_maximal_geodesic p) : ∃ u v : V, x = Sum.inr u ∧ y = Sum.inr v ∧ u ≠ v
- Formalizes
- arXiv:2610.36821 Section 5 (The Edge Geodesic Transversal Problem)
- Verified
- 29 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…
- 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.
- Used by 2
- corona_k1_exists_maximal_geodesicFor 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…
- corona_k1_exists_edge_geodesic_transversalFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, there exists a finset S of edges of the corona…
Read back from the Lean
Let $V$ be a finite type and $G$ be a connected simple graph on $V$ with $|V| \ge 2$. Let $x, y \in V \oplus V$, and let $p$ be a walk from $x$ to $y$ in the graph $\text{corona\_k1}(G)$. If $p$ is a maximal geodesic (that is, $p$ is a path of length equal to the distance between $x$ and $y$ in $\text{corona\_k1}(G)$, and no neighbor of $x$ is strictly further from $y$ than $x$ is, and no neighbor of $y$ is strictly further from $x$ than $y$ is), then there exist distinct vertices $u, v \in V$ ($u \neq v$) such that $x = \text{Sum.inr } u$ and $y = \text{Sum.inr } v$ (i.e., both endpoints of $p$ are distinct pendant vertices added in the corona product).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
In the corona graph G ⊙ K₁, every vertex u of the connected graph G is attached to a unique pendant leaf inr(u). The theorem proves that every maximal geodesic p must connect two distinct pendant leaves. First, no maximal geodesic can have an internal vertex inl(u) as an endpoint: extending towards its leaf inr(u) strictly increases distance unless the other endpoint is inr(u) itself, which is in turn ruled out by extending towards an adjacent neighbor in G. By path reversal, both endpoints must therefore be leaves, and they cannot be the same leaf because a trivial walk of length 0 cannot be maximal next to an adjacent vertex.
Reversing a maximal geodesic yields a maximal geodesic.
Reversing a walk preserves pathhood and length, and graph distance is symmetric, so the reversed walk remains a shortest path between its endpoints. By the symmetry of adjacency and distance in simple graphs, the conditions that no neighbor of an endpoint can be strictly farther away than the geodesic length translate directly to the endpoints of the reversed walk.
refine ⟨⟨hp.1.1.reverse, ?_⟩, ?_, ?_⟩ · rw [p.length_reverse, hp.1.2, G.dist_comm] · intro w hw rw [p.length_reverse] have := hp.2.2 w (G.adj_symm hw) rwa [G.dist_comm] · intro w hw rw [p.length_reverse] have := hp.2.1 w (G.adj_symm hw) rwa [G.dist_comm]
In a connected graph on at least two vertices, every vertex has a neighbor.
Because |V| ≥ 2, the vertex type V is nontrivial, so there exists some vertex v ≠ u. By connectedness, there exists a walk from u to v. Since the endpoints are distinct, this walk cannot be empty (nil); its first step therefore provides a vertex adjacent to u.
uses
Fintype.one_lt_card_iff_nontrivial.mp,Nat.succ_le_iff.mp,exists_nehave : Nontrivial V := Fintype.one_lt_card_iff_nontrivial.mp (Nat.succ_le_iff.mp hn) obtain ⟨v, hv⟩ := exists_ne u obtain ⟨p⟩ := hG u v cases p with | nil => contradiction | cons hadj rest => exact ⟨_, hadj⟩
The only neighbor of a pendant leaf inr(u) in the corona graph is inl(u).
By the definition of adjacency in the corona graph G ⊙ K₁, pendant vertices in the right summand are never adjacent to each other. Furthermore, inr(u) is adjacent to inl(v) in the left summand if and only if u = v. Thus any neighbor w of inr(u) must equal inl(u).
uses
congr_argcases w with | inl v => exact congr_arg Sum.inl (h : u = v).symm | inr v => cases h
Any walk from a pendant leaf inr(u) to y ≠ inr(u) has length at least dist(inl(u), y) + 1.
Because y ≠ inr(u), the walk cannot be empty. Its first step must be an edge from inr(u) to its unique neighbor inl(u). The remainder of the walk goes from inl(u) to y and has length at least the graph distance dist(inl(u), y), so the whole walk has length at least dist(inl(u), y) + 1.
uses
corona_k1_maximal_geodesic_endpoints_adj_inr_inv,SimpleGraph.Walk.length_conscases q with | nil => contradiction | cons hadj rest => have := corona_k1_maximal_geodesic_endpoints_adj_inr_inv G u hadj subst this have := (corona_k1 G).dist_le rest simp only [SimpleGraph.Walk.length_cons] omega
No maximal geodesic can start at an internal vertex inl(u) and end at y ≠ inr(u).
The leaf inr(u) is adjacent to inl(u), so prepending this edge to p gives a walk from inr(u) to y. A shortest walk q from inr(u) to y has length dist(inr(u), y) ≥ dist(inl(u), y) + 1. But by the maximality of p at inl(u), the distance from the neighbor inr(u) to y cannot exceed length(p) = dist(inl(u), y). This yields dist(inl(u), y) + 1 ≤ dist(inl(u), y), a contradiction.
uses
SimpleGraph.Walk.cons,corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_lehave hadj : (corona_k1 G).Adj (Sum.inr u) (Sum.inl u) := rfl have hr : (corona_k1 G).Reachable (Sum.inr u) y := ⟨SimpleGraph.Walk.cons hadj p⟩ obtain ⟨q, hq⟩ := hr.exists_walk_length_eq_dist have hlen := corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le G u y q hy rw [hq] at hlen have hmax := hp.2.1 (Sum.inr u) hadj have hlen_p := hp.1.2 omega
A maximal geodesic from inl(u) to inr(u) would have length 1, and any neighbor v of u in G would satisfy dist(inl(v), inr(u)) < 2.
Since G is connected with at least two vertices, u has some neighbor v in G, making inl(v) adjacent to inl(u) in the corona graph. The geodesic p between adjacent vertices inl(u) and inr(u) has length 1. By the maximality of p at inl(u), dist(inl(v), inr(u)) ≤ length(p) = 1, so this distance is strictly less than 2.
uses
corona_k1_maximal_geodesic_endpoints_exists_adj_of_connected,SimpleGraph.dist_eq_one_iff_adj.mprobtain ⟨v, huv⟩ := corona_k1_maximal_geodesic_endpoints_exists_adj_of_connected G hG hn u have hadj_w : (corona_k1 G).Adj (Sum.inl v) (Sum.inl u) := huv.symm have hdist_w := hp.2.1 (Sum.inl v) hadj_w have hp_len : p.length = 1 := by rw [hp.1.2] exact SimpleGraph.dist_eq_one_iff_adj.mpr (by exact rfl) rw [hp_len] at hdist_w have hlt : (corona_k1 G).dist (Sum.inl v) (Sum.inr u) < 2 := by omega
No maximal geodesic can run between inl(u) and inr(u).
We split into the two cases where dist(inl(v), inr(u)) is 0 or 1. A distance of 0 means the vertices are identical (impossible since inl ≠ inr) or unreachable (contradicted by the walk inl(v) → inl(u) → inr(u)). A distance of 1 means inl(v) is adjacent to inr(u), which by definition of the corona adjacency forces v = u, contradicting that G is loopless with an edge between u and v. Both cases are impossible.
uses
SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable,SimpleGraph.Walk.cons,SimpleGraph.Walk.nil,SimpleGraph.dist_eq_one_iff_adjinterval_cases hd : (corona_k1 G).dist (Sum.inl v) (Sum.inr u) · rw [SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable] at hd rcases hd with h1 | h2 · contradiction · apply h2 have h1 : (corona_k1 G).Adj (Sum.inl v) (Sum.inl u) := huv.symm have h2 : (corona_k1 G).Adj (Sum.inl u) (Sum.inr u) := rfl exact ⟨SimpleGraph.Walk.cons h1 (SimpleGraph.Walk.cons h2 SimpleGraph.Walk.nil)⟩ · rw [SimpleGraph.dist_eq_one_iff_adj] at hd have : (v = u) := hd subst this exact G.loopless.irrefl _ huv
No maximal geodesic can start at an internal vertex inl(u).
We split on whether the endpoint y equals inr(u). If y = inr(u), it is ruled out by the impossibility of a maximal geodesic between an internal vertex and its own leaf; if y ≠ inr(u), it is ruled out by the previous lemma for distinct destinations.
uses
corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_inr,corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_of_neby_cases hy : y = Sum.inr u · subst hy exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_inr G hG hn u p hp · exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_of_ne G u y p hy hp
No maximal geodesic can start and end at the same pendant leaf inr(u).
A walk from inr(u) to itself has length 0, so length(p) = 0. However, the internal vertex inl(u) is adjacent to inr(u), so their distance is 1. Maximality of p at inr(u) requires 1 = dist(inl(u), inr(u)) ≤ length(p) = 0, which is impossible.
uses
SimpleGraph.dist_self,SimpleGraph.dist_eq_one_iff_adj.mprhave hadj : (corona_k1 G).Adj (Sum.inl u) (Sum.inr u) := rfl have hdist := hp.2.1 (Sum.inl u) hadj have hlen : p.length = 0 := by rw [hp.1.2] exact SimpleGraph.dist_self rw [hlen] at hdist have hadj_dist : (corona_k1 G).dist (Sum.inl u) (Sum.inr u) = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr hadj omega
The starting vertex x of any maximal geodesic must be a pendant leaf inr(u).
We analyze the cases for x. If x were an internal vertex inl(u), it would contradict the lemma establishing that no maximal geodesic can start at an internal vertex. Therefore, x must be of the form inr(u).
uses
corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inlcases x with | inl u => exfalso exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl G hG hn u y p hp
The ending vertex y of any maximal geodesic must be a pendant leaf inr(v).
We analyze the cases for y. If y were an internal vertex inl(v), the reversed walk p.reverse would be a maximal geodesic starting at inl(v). But this contradicts the lemma forbidding maximal geodesics starting at internal vertices. Thus y must also be a leaf inr(v).
uses
corona_k1_maximal_geodesic_endpoints_is_maximal_geodesic_reverse,corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inlcases y with | inl v => exfalso have hp_rev := corona_k1_maximal_geodesic_endpoints_is_maximal_geodesic_reverse hp exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl G hG hn v (Sum.inr u) p.reverse hp_rev
Every maximal geodesic in G ⊙ K₁ has distinct pendant leaf endpoints: x = inr(u), y = inr(v), and u ≠ v.
Having established that x = inr(u) and y = inr(v), we supply u and v as the required witnesses. If u = v, the geodesic would start and end at the same leaf inr(u), which was proven impossible. Hence u ≠ v.
uses
corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inr_selfrefine ⟨u, v, rfl, rfl, ?_⟩ rintro rfl exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inr_self G u p hp
Fintype.one_lt_card_iff_nontrivial.mp- A finite type with cardinality strictly greater than 1 is nontrivial (contains at least two distinct elements).
Nat.succ_le_iff.mp- If the successor of a is at most b, then a < b; in particular, 2 ≤ |V| implies 1 < |V|.
exists_ne- In a nontrivial type, for every element x there exists another element y ≠ x.
congr_arg- Applying a function to equal arguments produces equal results.
corona_k1_maximal_geodesic_endpoints_adj_inr_inv- The only neighbor of a pendant vertex inr(u) in the corona graph G ⊙ K₁ is inl(u).
SimpleGraph.Walk.length_cons- Prepending an edge to a walk increases its length by 1.
SimpleGraph.Walk.cons- Prepends an adjacent edge to a walk, creating a walk from the new vertex.
corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le- Any walk in G ⊙ K₁ from a leaf inr(u) to a vertex y ≠ inr(u) has length at least dist(inl(u), y) + 1.
corona_k1_maximal_geodesic_endpoints_exists_adj_of_connected- In a connected graph on at least 2 vertices, every vertex has at least one neighbor.
SimpleGraph.dist_eq_one_iff_adj.mpr- If two vertices are adjacent, the graph distance between them is 1.
SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable- The graph distance between two vertices is 0 if and only if they are equal or unreachable from each other.
SimpleGraph.Walk.nil- The empty walk of length 0 from a vertex to itself.
SimpleGraph.dist_eq_one_iff_adj- Two vertices in a graph have distance 1 if and only if they are adjacent.
corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_inr- No maximal geodesic in G ⊙ K₁ can run between an internal vertex inl(u) and its pendant leaf inr(u).
corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_of_ne- No maximal geodesic in G ⊙ K₁ can start at an internal vertex inl(u) and end at any vertex other than inr(u).
SimpleGraph.dist_self- The graph distance from any vertex to itself is 0.
corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl- No maximal geodesic in G ⊙ K₁ can start at an internal vertex inl(u).
corona_k1_maximal_geodesic_endpoints_is_maximal_geodesic_reverse- Reversing a maximal geodesic yields another maximal geodesic.
corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inr_self- No maximal geodesic in G ⊙ K₁ can start and end at the same pendant leaf inr(u).
- Contradictory distance bounds (such as d + 1 ≤ d' ≤ d or 1 ≤ 0) are closed by linear arithmetic via `omega`.
- The contradiction for dist(inl v, inr u) < 2 uses `interval_cases` to split into the discrete distance cases 0 and 1.
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.
lemma corona_k1_maximal_geodesic_endpoints_is_maximal_geodesic_reverse {V : Type*} {G : SimpleGraph V} {u v : V} {p : G.Walk u v} (hp : is_maximal_geodesic p) : is_maximal_geodesic p.reverse := by refine ⟨⟨hp.1.1.reverse, ?_⟩, ?_, ?_⟩ · rw [p.length_reverse, hp.1.2, G.dist_comm] · intro w hw rw [p.length_reverse] have := hp.2.2 w (G.adj_symm hw) rwa [G.dist_comm] · intro w hw rw [p.length_reverse] have := hp.2.1 w (G.adj_symm hw) rwa [G.dist_comm]lemma corona_k1_maximal_geodesic_endpoints_exists_adj_of_connected {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) (u : V) : ∃ v : V, G.Adj u v := by have : Nontrivial V := Fintype.one_lt_card_iff_nontrivial.mp (Nat.succ_le_iff.mp hn) obtain ⟨v, hv⟩ := exists_ne u obtain ⟨p⟩ := hG u v cases p with | nil => contradiction | cons hadj rest => exact ⟨_, hadj⟩lemma corona_k1_maximal_geodesic_endpoints_adj_inr_inv {V : Type*} (G : SimpleGraph V) (u : V) {w : V ⊕ V} (h : (corona_k1 G).Adj (Sum.inr u) w) : w = Sum.inl u := by cases w with | inl v => exact congr_arg Sum.inl (h : u = v).symm | inr v => cases hlemma corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le {V : Type*} (G : SimpleGraph V) (u : V) (y : V ⊕ V) (q : (corona_k1 G).Walk (Sum.inr u) y) (hy : y ≠ Sum.inr u) : (corona_k1 G).dist (Sum.inl u) y + 1 ≤ q.length := by cases q with | nil => contradiction | cons hadj rest => have := corona_k1_maximal_geodesic_endpoints_adj_inr_inv G u hadj subst this have := (corona_k1 G).dist_le rest simp only [SimpleGraph.Walk.length_cons] omegalemma corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_of_ne {V : Type*} (G : SimpleGraph V) (u : V) (y : V ⊕ V) (p : (corona_k1 G).Walk (Sum.inl u) y) (hy : y ≠ Sum.inr u) (hp : is_maximal_geodesic p) : False := by have hadj : (corona_k1 G).Adj (Sum.inr u) (Sum.inl u) := rfl have hr : (corona_k1 G).Reachable (Sum.inr u) y := ⟨SimpleGraph.Walk.cons hadj p⟩ obtain ⟨q, hq⟩ := hr.exists_walk_length_eq_dist have hlen := corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le G u y q hy rw [hq] at hlen have hmax := hp.2.1 (Sum.inr u) hadj have hlen_p := hp.1.2 omegalemma corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_inr {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) (u : V) (p : (corona_k1 G).Walk (Sum.inl u) (Sum.inr u)) (hp : is_maximal_geodesic p) : False := by obtain ⟨v, huv⟩ := corona_k1_maximal_geodesic_endpoints_exists_adj_of_connected G hG hn u have hadj_w : (corona_k1 G).Adj (Sum.inl v) (Sum.inl u) := huv.symm have hdist_w := hp.2.1 (Sum.inl v) hadj_w have hp_len : p.length = 1 := by rw [hp.1.2] exact SimpleGraph.dist_eq_one_iff_adj.mpr (by exact rfl) rw [hp_len] at hdist_w have hlt : (corona_k1 G).dist (Sum.inl v) (Sum.inr u) < 2 := by omega interval_cases hd : (corona_k1 G).dist (Sum.inl v) (Sum.inr u) · rw [SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable] at hd rcases hd with h1 | h2 · contradiction · apply h2 have h1 : (corona_k1 G).Adj (Sum.inl v) (Sum.inl u) := huv.symm have h2 : (corona_k1 G).Adj (Sum.inl u) (Sum.inr u) := rfl exact ⟨SimpleGraph.Walk.cons h1 (SimpleGraph.Walk.cons h2 SimpleGraph.Walk.nil)⟩ · rw [SimpleGraph.dist_eq_one_iff_adj] at hd have : (v = u) := hd subst this exact G.loopless.irrefl _ huvlemma corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) (u : V) (y : V ⊕ V) (p : (corona_k1 G).Walk (Sum.inl u) y) (hp : is_maximal_geodesic p) : False := by by_cases hy : y = Sum.inr u · subst hy exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_inr G hG hn u p hp · exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_of_ne G u y p hy hplemma corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inr_self {V : Type*} (G : SimpleGraph V) (u : V) (p : (corona_k1 G).Walk (Sum.inr u) (Sum.inr u)) (hp : is_maximal_geodesic p) : False := by have hadj : (corona_k1 G).Adj (Sum.inl u) (Sum.inr u) := rfl have hdist := hp.2.1 (Sum.inl u) hadj have hlen : p.length = 0 := by rw [hp.1.2] exact SimpleGraph.dist_self rw [hlen] at hdist have hadj_dist : (corona_k1 G).dist (Sum.inl u) (Sum.inr u) = 1 := SimpleGraph.dist_eq_one_iff_adj.mpr hadj omega/-- Every maximal geodesic in G ⊙ K_1 has both endpoints at distinct pendant leaves. -/theorem corona_k1_maximal_geodesic_endpoints {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) (hp : is_maximal_geodesic p) : ∃ u v : V, x = Sum.inr u ∧ y = Sum.inr v ∧ u ≠ v := by cases x with | inl u => exfalso exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl G hG hn u y p hp | inr u => cases y with | inl v => exfalso have hp_rev := corona_k1_maximal_geodesic_endpoints_is_maximal_geodesic_reverse hp exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl G hG hn v (Sum.inr u) p.reverse hp_rev | inr v => refine ⟨u, v, rfl, rfl, ?_⟩ rintro rfl exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inr_self G u p hp