AFTD Auto-Formalizing Theoretical Domains

edge_geodesic_transversal_number_corona_k1_card_two

theoremverified

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.

  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.

    lines 5–7

    uses edge_geodesic_transversal_number_corona_k1_le

      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
  2. 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.

    lines 8–12

    uses le_csInf, corona_k1_exists_edge_geodesic_transversal

      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⟩
  3. 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.

    lines 13–17

    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⟩
  4. 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.

    line 18

      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

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