edge_geodesic_transversal_number_corona_k1_le
For 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 product corona_k1 G satisfies edge_geodesic_transversal_number (corona_k1 G) ≤ Fintype.card V - 1.
Statement
theorem edge_geodesic_transversal_number_corona_k1_le {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) : edge_geodesic_transversal_number (corona_k1 G) ≤ 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…
- 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…
- 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.
- Used by 1
- 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…
Read back from the Lean
For any finite type $V$ and any connected simple graph $G$ on $V$ such that the number of vertices $|V| \ge 2$, the edge geodesic transversal number of the corona graph $\text{corona\_k1}(G)$ is at most $|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
The edge geodesic transversal number of a graph is defined as the infimum of the cardinalities of all its edge geodesic transversals. Applying the lemma `corona_k1_exists_edge_geodesic_transversal` provides a transversal of G ⊙ K₁ with cardinality |V| - 1. Since this cardinality belongs to the set defining the transversal number, the infimum is at most |V| - 1.
There exists an edge geodesic transversal S of the corona graph G ⊙ K₁ with cardinality |V| - 1.
Applying `corona_k1_exists_edge_geodesic_transversal` to the connected graph G with |V| ≥ 2 provides an edge set S that is an edge geodesic transversal of G ⊙ K₁ and has size |S| = |V| - 1.
uses
corona_k1_exists_edge_geodesic_transversalobtain ⟨S, hS, hcard⟩ := corona_k1_exists_edge_geodesic_transversal G hG hnThe edge geodesic transversal number of G ⊙ K₁ is at most |V| - 1.
By definition, the edge geodesic transversal number is the infimum of the sizes of all edge geodesic transversals. The transversal S witnesses that |V| - 1 belongs to the set of such sizes; by `Nat.sInf_le`, the infimum of the set is at most this element.
uses
Nat.sInf_leexact Nat.sInf_le ⟨S, hS, hcard⟩
corona_k1_exists_edge_geodesic_transversal- For any connected graph G on a finite vertex type V with |V| ≥ 2, there exists an edge geodesic transversal of the corona graph G ⊙ K₁ with cardinality |V| - 1.
Nat.sInf_le- If a natural number m belongs to a set s of natural numbers, then the infimum (sInf) of s is at most m.
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 is at most |V| - 1. -/theorem edge_geodesic_transversal_number_corona_k1_le {V : Type*} [Fintype V] (G : SimpleGraph V) (hG : G.Connected) (hn : 2 ≤ Fintype.card V) : edge_geodesic_transversal_number (corona_k1 G) ≤ Fintype.card V - 1 := by obtain ⟨S, hS, hcard⟩ := corona_k1_exists_edge_geodesic_transversal G hG hn exact Nat.sInf_le ⟨S, hS, hcard⟩