AFTD Auto-Formalizing Theoretical Domains

corona_k1_exists_edge_geodesic_transversal

theoremverifiedformalization

For 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 product corona_k1 G such that is_edge_geodesic_transversal (corona_k1 G) S and S.card = Fintype.card V - 1.

Statement

theorem corona_k1_exists_edge_geodesic_transversal
    {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) :
    ∃ S : Finset (Sym2 (V ⊕ V)), is_edge_geodesic_transversal (corona_k1 G) S ∧ S.card = Fintype.card V - 1
Formalizes
arXiv:2610.36821 Section 5 (The Edge Geodesic Transversal Problem)
Verified
29 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_edge_geodesic_transversalA finite set S of edges of G is an edge geodesic transversal if every maximal geodesic in G contains at least one edge of S.
  • 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…
  • 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

For any finite type $V$ and any connected simple graph $G$ on $V$ with $|V| \ge 2$, there exists a finite set $S$ of unordered pairs of vertices in $V \oplus V$ such that: 1. $S$ is an "edge geodesic transversal" of the corona graph $\operatorname{corona\_k1}(G)$ (meaning every element of $S$ is an edge of $\operatorname{corona\_k1}(G)$, and for every pair of vertices $u, v \in V \oplus V$ and every walk $p$ from $u$ to $v$ in $\operatorname{corona\_k1}(G)$, if $p$ is a path whose length equals the graph distance between $u$ and $v$, every neighbor of $u$ has distance to $v$ at most the length of $p$, and every neighbor of $v$ has distance to $u$ at most the length of $p$, then at least one edge of $p$ belongs to $S$); 2. The cardinality of $S$ equals $|V| - 1$.

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

To construct an edge geodesic transversal of size |V| - 1 in the corona graph G ⊙ K_1, fix an arbitrary vertex w0 ∈ V and select the set S consisting of all leaf edges s(inl(v), inr(v)) for v ∈ V \ {w0}. By injectivity of the leaf edge assignment, |S| = |V| - 1. Any maximal geodesic in G ⊙ K_1 must connect two distinct leaves inr(u) and inr(v) with u ≠ v. Since at least one of u or v is not w0, and any walk leaving a leaf must immediately traverse its incident leaf edge, the path (or its reverse) necessarily contains an edge from S.

  1. Any walk in G ⊙ K_1 starting at a leaf inr(u) and ending at a different vertex must contain the leaf edge s(inl(u), inr(u)).

    We proceed by cases on the walk p. The trivial (nil) walk has identical endpoints, which contradicts the hypothesis that the destination differs from inr(u). In the non-trivial case, the first step goes to some neighbor w. By definition of the corona product, leaf vertices have no edges between them and inr(u) is adjacent only to inl(u), forcing w = inl(u). Hence the walk's first edge is s(inr(u), inl(u)) = s(inl(u), inr(u)).

    lines 1–17

    uses False.elim, Sym2.eq_swap

    theorem corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk {V : Type*} (G : SimpleGraph V) {u : V} {y : V ⊕ V}
        (p : (corona_k1 G).Walk (Sum.inr u) y) (hy : y ≠ Sum.inr u) :
        s(Sum.inl u, Sum.inr u) ∈ p.edges := by
      cases p with
      | nil => contradiction
      | cons h p' =>
        rename_i w
        have hw : w = Sum.inl u := by
          cases w with
          | inl w =>
            have : u = w := h
            rw [this]
          | inr w =>
            exact False.elim h
        subst hw
        rw [Sym2.eq_swap]
        simp [SimpleGraph.Walk.edges]
  2. There exists a base vertex w0 ∈ V, the leaf-edge map f : v ↦ s(inl(v), inr(v)) is injective, and S is defined as the image of V \ {w0} under f.

    Since |V| ≥ 2, V is nonempty, allowing us to choose a base vertex w0 ∈ V. We define f mapping each vertex v to its incident pendant edge s(inl(v), inr(v)). If f(a) = f(b), then either the endpoints match directly (giving a = b) or with swapped tags; the swapped case is impossible since inl(a) = inr(b) cannot hold in a disjoint sum. Thus f is injective, and we define S as the image under f of V \ {w0}.

    lines 18–33

    uses Fintype.card_pos_iff.mp, Sym2.eq_iff

    /-- There exists an edge geodesic transversal of G ⊙ K_1 of cardinality |V| - 1. -/
    theorem corona_k1_exists_edge_geodesic_transversal
        {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) :
        ∃ S : Finset (Sym2 (V ⊕ V)), is_edge_geodesic_transversal (corona_k1 G) S ∧ S.card = Fintype.card V - 1 := open SimpleGraph in by
      classical
      have : Nonempty V := Fintype.card_pos_iff.mp (by omega)
      obtain ⟨w0⟩ := this
      let f : V → Sym2 (V ⊕ V) := fun v => s(Sum.inl v, Sum.inr v)
      have hf_inj : Function.Injective f := by
        intro a b hab
        rw [Sym2.eq_iff] at hab
        rcases hab with ⟨h1, -⟩ | ⟨h1, -⟩
        · cases h1; rfl
        · cases h1
      let S := (Finset.univ.erase w0).image f
  3. Every element of S is an edge of the corona graph corona_k1(G).

    We provide S as the candidate witness. Any e ∈ S is of the form f(w) = s(inl(w), inr(w)) for some w ∈ V \ {w0}. By definition of the corona product, inl(w) and inr(w) are adjacent, so e is indeed in the edge set of corona_k1(G).

    lines 34–40

    uses Finset.mem_image, mem_edgeSet

      refine ⟨S, ⟨?_, ?_⟩, ?_⟩
      · intro e he
        rw [Finset.mem_image] at he
        obtain ⟨w, -, rfl⟩ := he
        rw [mem_edgeSet]
        show (corona_k1 G).Adj (Sum.inl w) (Sum.inr w)
        rfl
  4. Any maximal geodesic in G ⊙ K_1 has its endpoints at two distinct leaf vertices inr(u) and inr(v) with u ≠ v.

    Let p be a maximal geodesic. By corona_k1_maximal_geodesic_endpoints, since G is connected and |V| ≥ 2, the endpoints of p cannot be internal vertices and must be two distinct leaves inr(u) and inr(v) with u ≠ v.

    lines 41–43

    uses corona_k1_maximal_geodesic_endpoints

      · intro x y p hp
        have hp_max : is_maximal_geodesic p := ⟨⟨hp.1, hp.2.1⟩, hp.2.2⟩
        obtain ⟨u, v, rfl, rfl, huv⟩ := corona_k1_maximal_geodesic_endpoints G hG hn p hp_max
  5. If the starting leaf is inr(w0), the maximal geodesic contains the target leaf edge f(v), which belongs to S.

    In the case u = w0, since u ≠ v, the other endpoint v is not w0, so f(v) ∈ S. The reversed walk p.reverse starts at inr(v) and ends at inr(u) ≠ inr(v). By the preliminary lemma, the leaf edge f(v) belongs to the edges of p.reverse, and reversing back shows f(v) belongs to the edges of p.

    lines 44–53

    uses Finset.mem_image, Finset.mem_erase.mpr, Finset.mem_univ, corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk, Walk.edges_reverse, List.mem_reverse

        by_cases hu : u = w0
        · have hv : v ≠ w0 := by rintro rfl; exact huv hu
          refine ⟨f v, ?_, ?_⟩
          · rw [Finset.mem_image]
            exact ⟨v, Finset.mem_erase.mpr ⟨hv, Finset.mem_univ v⟩, rfl⟩
          · have hx : (Sum.inr u : V ⊕ V) ≠ Sum.inr v := by
              intro h; injection h with h'; exact huv h'
            have h_rev := corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk G p.reverse hx
            rw [Walk.edges_reverse, List.mem_reverse] at h_rev
            exact h_rev
  6. If the starting leaf is inr(u) with u ≠ w0, the maximal geodesic contains the source leaf edge f(u), which belongs to S.

    In the case u ≠ w0, the leaf edge f(u) directly belongs to S. Since the walk p starts at inr(u) and ends at inr(v) ≠ inr(u), the preliminary lemma guarantees that f(u) is an edge of p.

    lines 54–59

    uses Finset.mem_image, Finset.mem_erase.mpr, Finset.mem_univ, corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk

        · refine ⟨f u, ?_, ?_⟩
          · rw [Finset.mem_image]
            exact ⟨u, Finset.mem_erase.mpr ⟨hu, Finset.mem_univ u⟩, rfl⟩
          · have hy : (Sum.inr v : V ⊕ V) ≠ Sum.inr u := by
              intro h; injection h with h'; exact huv.symm h'
            exact corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk G p hy
  7. The cardinality of S is |V| - 1.

    Because f is injective, the cardinality of S = f(V \ {w0}) equals that of V \ {w0}. Since w0 is an element of the universe V, removing it decreases the cardinality from |V| to |V| - 1.

    lines 60–61

    uses Finset.card_image_of_injective, Finset.card_erase_of_mem, Finset.mem_univ, Fintype.card

      · rw [Finset.card_image_of_injective _ hf_inj]
        rw [Finset.card_erase_of_mem (Finset.mem_univ w0), Fintype.card]
False.elim
From a contradiction (False), any proposition can be deduced.
Sym2.eq_swap
Unordered pairs are symmetric: s(a, b) = s(b, a).
Fintype.card_pos_iff.mp
If the cardinality of a finite type is strictly positive, the type is nonempty.
Sym2.eq_iff
Two unordered pairs s(x, y) and s(z, w) are equal if and only if (x = z ∧ y = w) or (x = w ∧ y = z).
Finset.mem_image
An element b belongs to the image f(s) if and only if b = f(a) for some a ∈ s.
mem_edgeSet
An unordered pair s(v, w) belongs to the edge set of a graph if and only if v and w are adjacent.
corona_k1_maximal_geodesic_endpoints
In the corona product G ⊙ K_1 of a connected graph G with at least two vertices, every maximal geodesic has its endpoints at two distinct leaf vertices inr(u) and inr(v) with u ≠ v.
Finset.mem_erase.mpr
An element belongs to s \ {a} if it belongs to s and differs from a.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk
Any walk in G ⊙ K_1 starting at a leaf inr(u) and ending at a different vertex contains the incident leaf edge s(inl(u), inr(u)).
Walk.edges_reverse
The edges of the reversal of a walk p form the reversal of the edge list of p.
List.mem_reverse
An element belongs to the reverse of a list if and only if it belongs to the list.
Finset.card_image_of_injective
The image of a finite set under an injective function has the same cardinality as the set.
Finset.card_erase_of_mem
Erasing an element from a finite set that contains it decreases its cardinality by 1.
Fintype.card
The cardinality of a finite type equals the cardinality of its universal finset.

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

theorem corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk {V : Type*} (G : SimpleGraph V) {u : V} {y : V ⊕ V}    (p : (corona_k1 G).Walk (Sum.inr u) y) (hy : y ≠ Sum.inr u) :    s(Sum.inl u, Sum.inr u) ∈ p.edges := by  cases p with  | nil => contradiction  | cons h p' =>    rename_i w    have hw : w = Sum.inl u := by      cases w with      | inl w =>        have : u = w := h        rw [this]      | inr w =>        exact False.elim h    subst hw    rw [Sym2.eq_swap]    simp [SimpleGraph.Walk.edges]/-- There exists an edge geodesic transversal of G ⊙ K_1 of cardinality |V| - 1. -/theorem corona_k1_exists_edge_geodesic_transversal    {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) :    ∃ S : Finset (Sym2 (V ⊕ V)), is_edge_geodesic_transversal (corona_k1 G) S ∧ S.card = Fintype.card V - 1 := open SimpleGraph in by  classical  have : Nonempty V := Fintype.card_pos_iff.mp (by omega)  obtain ⟨w0⟩ := this  let f : V → Sym2 (V ⊕ V) := fun v => s(Sum.inl v, Sum.inr v)  have hf_inj : Function.Injective f := by    intro a b hab    rw [Sym2.eq_iff] at hab    rcases hab with ⟨h1, -⟩ | ⟨h1, -⟩    · cases h1; rfl    · cases h1  let S := (Finset.univ.erase w0).image f  refine ⟨S, ⟨?_, ?_⟩, ?_⟩  · intro e he    rw [Finset.mem_image] at he    obtain ⟨w, -, rfl⟩ := he    rw [mem_edgeSet]    show (corona_k1 G).Adj (Sum.inl w) (Sum.inr w)    rfl  · intro x y p hp    have hp_max : is_maximal_geodesic p := ⟨⟨hp.1, hp.2.1⟩, hp.2.2⟩    obtain ⟨u, v, rfl, rfl, huv⟩ := corona_k1_maximal_geodesic_endpoints G hG hn p hp_max    by_cases hu : u = w0    · have hv : v ≠ w0 := by rintro rfl; exact huv hu      refine ⟨f v, ?_, ?_⟩      · rw [Finset.mem_image]        exact ⟨v, Finset.mem_erase.mpr ⟨hv, Finset.mem_univ v⟩, rfl⟩      · have hx : (Sum.inr u : V ⊕ V) ≠ Sum.inr v := by          intro h; injection h with h'; exact huv h'        have h_rev := corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk G p.reverse hx        rw [Walk.edges_reverse, List.mem_reverse] at h_rev        exact h_rev    · refine ⟨f u, ?_, ?_⟩      · rw [Finset.mem_image]        exact ⟨u, Finset.mem_erase.mpr ⟨hu, Finset.mem_univ u⟩, rfl⟩      · have hy : (Sum.inr v : V ⊕ V) ≠ Sum.inr u := by          intro h; injection h with h'; exact huv.symm h'        exact corona_k1_exists_edge_geodesic_transversal_leaf_edge_in_walk G p hy  · rw [Finset.card_image_of_injective _ hf_inj]    rw [Finset.card_erase_of_mem (Finset.mem_univ w0), Fintype.card]
See it in the graphDiscuss this resultChallenge it