AFTD Auto-Formalizing Theoretical Domains

corona_k1_maximal_geodesic_endpoints

theoremverifiedformalization

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

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.

  1. 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.

    lines 3–12

      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]
  2. 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.

    lines 16–21

    uses Fintype.one_lt_card_iff_nontrivial.mp, Nat.succ_le_iff.mp, exists_ne

      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⟩
  3. 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).

    lines 25–27

    uses congr_arg

      cases w with
      | inl v => exact congr_arg Sum.inl (h : u = v).symm
      | inr v => cases h
  4. 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.

    lines 32–39

    uses corona_k1_maximal_geodesic_endpoints_adj_inr_inv, SimpleGraph.Walk.length_cons

      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]
        omega
  5. 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.

    lines 44–51

    uses SimpleGraph.Walk.cons, corona_k1_maximal_geodesic_endpoints_walk_from_inr_length_le

      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
      omega
  6. 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.

    lines 56–63

    uses corona_k1_maximal_geodesic_endpoints_exists_adj_of_connected, SimpleGraph.dist_eq_one_iff_adj.mpr

      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
  7. 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.

    lines 64–75

    uses SimpleGraph.dist_eq_zero_iff_eq_or_not_reachable, SimpleGraph.Walk.cons, SimpleGraph.Walk.nil, SimpleGraph.dist_eq_one_iff_adj

      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 _ huv
  8. 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.

    lines 80–83

    uses corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_inr, corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl_of_ne

      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 hp
  9. 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.

    lines 87–95

    uses SimpleGraph.dist_self, SimpleGraph.dist_eq_one_iff_adj.mpr

      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
  10. 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).

    lines 102–105

    uses corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl

      cases x with
      | inl u =>
        exfalso
        exact corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl G hG hn u y p hp
  11. 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).

    lines 107–111

    uses corona_k1_maximal_geodesic_endpoints_is_maximal_geodesic_reverse, corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inl

        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
  12. 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.

    lines 113–115

    uses corona_k1_maximal_geodesic_endpoints_not_maximal_geodesic_inr_self

          refine ⟨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).

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

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