edge_geodesic_transversal_number_corona_k1_card_two
For every finite type V with Fintype.card V = 2 and every connected simple graph G on V, the edge geodesic transversal number of the corona product corona_k1 G satisfies edge_geodesic_transversal_number (corona_k1 G) = 1.
Statement
theorem edge_geodesic_transversal_number_corona_k1_card_two {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : Fintype.card V = 2) : edge_geodesic_transversal_number (corona_k1 G) = 1
- Source
- arXiv:2610.36821 Section 5 (The Edge Geodesic Transversal Problem)
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- 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…
- edge_geodesic_transversal_numberThe edge geodesic transversal number of a simple graph G is the infimum in ℕ of the set of natural numbers k such that there exists a…
- 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…
- 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…
- 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_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…
- 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.
Read back from the Lean
For any finite type $V$ and any simple graph $G$ on $V$, if $G$ is connected and the cardinality of $V$ is 2, then the edge geodesic transversal number of the corona graph corona_k1 G is equal to 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
The proof establishes that the edge geodesic transversal number of G ⊙ K₁ is 1 by sandwiching it between 1 and 1. The upper bound follows from the general theorem that the transversal number of G ⊙ K₁ is at most |V| - 1, which equals 1 when |V| = 2. The lower bound holds because the transversal number is the infimum of sizes of edge geodesic transversals, and every such transversal must contain an edge from each maximal geodesic, guaranteeing that every transversal is nonempty and thus has size at least 1.
The edge geodesic transversal number of G ⊙ K₁ is at most 1
Since |V| = 2, we have 2 ≤ |V|. Applying the general upper bound edge_geodesic_transversal_number_corona_k1_le, which bounds the transversal number of G ⊙ K₁ by |V| - 1 for any connected graph with at least two vertices, and substituting |V| = 2, we get that the transversal number is at most 2 - 1 = 1.
uses
edge_geodesic_transversal_number_corona_k1_lehave h2 : 2 ≤ Fintype.card V := by omega have h_le := edge_geodesic_transversal_number_corona_k1_le G hG h2 rw [hn] at h_le
To show that the edge geodesic transversal number of G ⊙ K₁ is at least 1, it suffices to show that every edge geodesic transversal has cardinality at least 1
The edge geodesic transversal number is defined as the infimum of the sizes of all edge geodesic transversals. By le_csInf, this infimum is at least 1 provided the set of sizes is nonempty and 1 bounds each size from below. Nonemptiness is witnessed by corona_k1_exists_edge_geodesic_transversal, which guarantees that an edge geodesic transversal exists.
uses
le_csInf,corona_k1_exists_edge_geodesic_transversalhave h_ge : 1 ≤ edge_geodesic_transversal_number (corona_k1 G) := by unfold edge_geodesic_transversal_number apply le_csInf · rcases corona_k1_exists_edge_geodesic_transversal G hG h2 with ⟨S, hS, -⟩ exact ⟨S.card, S, hS, rfl⟩
Every edge geodesic transversal of G ⊙ K₁ has cardinality at least 1
Given any edge geodesic transversal S, the graph G ⊙ K₁ has at least one maximal geodesic path p by corona_k1_exists_maximal_geodesic. By definition of a transversal, S must contain at least one edge e of p. Since e ∈ S, the finite set S is nonempty, and Finset.card_pos.mpr implies |S| ≥ 1.
uses
corona_k1_exists_maximal_geodesic,Finset.card_pos.mpr· rintro k ⟨S, hS, rfl⟩ rcases corona_k1_exists_maximal_geodesic G hG h2 with ⟨x, y, p, hp⟩ rcases hp with ⟨⟨hp1, hp2⟩, hp3, hp4⟩ obtain ⟨e, heS, -⟩ := hS.2 p ⟨hp1, hp2, hp3, hp4⟩ exact Finset.card_pos.mpr ⟨e, heS⟩
The edge geodesic transversal number of G ⊙ K₁ equals 1
Combining the upper bound of at most 2 - 1 = 1 with the lower bound of at least 1, linear arithmetic over ℕ establishes that the transversal number is exactly 1.
omega
edge_geodesic_transversal_number_corona_k1_le- for any connected graph G on at least 2 vertices, the edge geodesic transversal number of the corona product G ⊙ K₁ is at most |V| - 1
le_csInf- a value a is less than or equal to the infimum of a nonempty set s if a is less than or equal to every element of s
corona_k1_exists_edge_geodesic_transversal- for any connected graph G on at least 2 vertices, there exists an edge geodesic transversal of G ⊙ K₁ of size |V| - 1
corona_k1_exists_maximal_geodesic- for any connected graph G on at least 2 vertices, the corona product G ⊙ K₁ contains at least one maximal geodesic walk
Finset.card_pos.mpr- a finite set has strictly positive cardinality if and only if it is nonempty
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.
/-- The edge geodesic transversal number of G ⊙ K_1 equals 1 when G has 2 vertices. -/theorem edge_geodesic_transversal_number_corona_k1_card_two {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : Fintype.card V = 2) : edge_geodesic_transversal_number (corona_k1 G) = 1 := by have h2 : 2 ≤ Fintype.card V := by omega have h_le := edge_geodesic_transversal_number_corona_k1_le G hG h2 rw [hn] at h_le have h_ge : 1 ≤ edge_geodesic_transversal_number (corona_k1 G) := by unfold edge_geodesic_transversal_number apply le_csInf · rcases corona_k1_exists_edge_geodesic_transversal G hG h2 with ⟨S, hS, -⟩ exact ⟨S.card, S, hS, rfl⟩ · rintro k ⟨S, hS, rfl⟩ rcases corona_k1_exists_maximal_geodesic G hG h2 with ⟨x, y, p, hp⟩ rcases hp with ⟨⟨hp1, hp2⟩, hp3, hp4⟩ obtain ⟨e, heS, -⟩ := hS.2 p ⟨hp1, hp2, hp3, hp4⟩ exact Finset.card_pos.mpr ⟨e, heS⟩ omega