AFTD Auto-Formalizing Theoretical Domains

edge_geodesic_transversal_number_corona_k1_le

theoremverifiedformalization

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

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.

  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.

    line 5

    uses corona_k1_exists_edge_geodesic_transversal

      obtain ⟨S, hS, hcard⟩ := corona_k1_exists_edge_geodesic_transversal G hG hn
  2. The 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.

    line 6

    uses Nat.sInf_le

      exact 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

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