corona_k1_exists_edge_geodesic_transversal
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
- 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…
- edge_geodesic_transversal_number_corona_k1_leFor every finite type V with 2 ≤ Fintype.card V and every connected simple graph G on V, the edge geodesic transversal number of the…
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.
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)).
uses
False.elim,Sym2.eq_swaptheorem 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 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}.
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
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).
uses
Finset.mem_image,mem_edgeSetrefine ⟨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
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.
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
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.
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_reverseby_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
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.
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
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.
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.
- The corona product `corona_k1 G` represents the graph G on the left summand `Sum.inl` and attaches a degree-1 pendant leaf vertex via `Sum.inr` to each vertex of G.
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.
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]