AFTD Auto-Formalizing Theoretical Domains

corona_k1_exists_maximal_geodesic

theoremverified

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

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.

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

    lines 5–6

    uses Fintype.one_lt_card_iff.mp

      obtain ⟨u, v, huv⟩ := Fintype.one_lt_card_iff.mp hn
      have h_reach_G : G.Reachable u v := hG u v
  2. 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.

    lines 7–11

    uses SimpleGraph.Reachable.map

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

    lines 12–16

    uses SimpleGraph.Walk.isPath_of_length_eq_dist

      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⟩, ?_, ?_⟩
  4. 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).

    lines 17–26

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

    lines 27–37

    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

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