AFTD Auto-Formalizing Theoretical Domains

geodesic_transversal_number_le_edge_geodesic_transversal_number

theoremverifiedformalization

For any connected simple graph G that admits a finite edge geodesic transversal, the vertex geodesic transversal number of G is bounded above by the edge geodesic transversal number of G, that is, gt(G) ≤ gt_e(G).

Statement

theorem geodesic_transversal_number_le_edge_geodesic_transversal_number {V : Type*} (G : SimpleGraph V) (hG : G.Connected) (hT : ∃ T : Finset (Sym2 V), is_edge_geodesic_transversal G T) : geodesic_transversal_number G ≤ edge_geodesic_transversal_number G
Formalizes
scout/2610-36821-the-edge-geodesic-transversal-problem.md:103
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • geodesic_transversal_numberThe geodesic transversal number gt(G) of a simple graph G is the infimum in ℕ of the set of natural numbers k such that there exists a…
  • 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…
  • exists_geodesic_transversal_of_edge_geodesic_transversalFor any finite edge geodesic transversal T in a simple graph G, there exists a finite vertex geodesic transversal S of G such that 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.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • is_geodesic_transversalA finite set S of vertices in a simple graph G is a geodesic transversal if every maximal geodesic in G contains at least one vertex of S.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

Read back from the Lean

For any type $V$ and any simple graph $G$ on $V$, if $G$ is connected and there exists a finite set of edges $T$ of $G$ that forms an edge geodesic transversal of $G$, then the geodesic transversal number of $G$ is less than or equal to the edge geodesic transversal number of $G$. Here: - A walk $p$ between vertices $u$ and $v$ is a *maximal geodesic* if it is a path, its length equals the graph distance $d_G(u, v)$, and it cannot be extended to a longer shortest path from either endpoint (i.e., for any neighbor $w$ of $u$, $d_G(w, v) \le \mathrm{length}(p)$, and for any neighbor $w$ of $v$, $d_G(u, w) \le \mathrm{length}(p)$). - A finite set of edges $S \subseteq E(G)$ is an *edge geodesic transversal* if every maximal geodesic walk in $G$ traverses at least one edge in $S$. - A finite set of vertices $S \subseteq V$ is a *geodesic transversal* if every maximal geodesic walk in $G$ visits at least one vertex in $S$. - The *geodesic transversal number* (resp. *edge geodesic transversal number*) is the infimum in $\mathbb{N}$ of the cardinalities of all finite geodesic transversals (resp. finite edge geodesic transversals) of $G$.

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 show that gt(G) ≤ gt_e(G), we consider an edge geodesic transversal T of minimum cardinality, so |T| = gt_e(G). By the lemma `exists_geodesic_transversal_of_edge_geodesic_transversal`, there exists a vertex geodesic transversal S with |S| ≤ |T|. Since gt(G) is defined as the infimum of the sizes of all vertex geodesic transversals, it is bounded above by |S|, which immediately yields gt(G) ≤ gt_e(G).

  1. The set of sizes of edge geodesic transversals of G is nonempty.

    We unfold the definition of `edge_geodesic_transversal_number` as the infimum of the set of cardinalities of all edge geodesic transversals. By unpacking the hypothesis that an edge geodesic transversal exists, we obtain a witness T0 whose cardinality shows that this set of natural numbers is nonempty.

    lines 3–7

      have _ := hG
      unfold edge_geodesic_transversal_number
      rcases hT with ⟨T0, hT0⟩
      have hne : { k : ℕ | ∃ S : Finset (Sym2 V), is_edge_geodesic_transversal G S ∧ S.card = k }.Nonempty := by
        exact ⟨T0.card, ⟨T0, hT0, rfl⟩⟩
  2. There exists an edge geodesic transversal T of minimal cardinality, satisfying |T| = gt_e(G).

    By `Nat.sInf_mem`, every nonempty subset of ℕ contains its infimum. Applying this to the set of sizes of edge geodesic transversals yields an edge geodesic transversal T whose cardinality equals the infimum, which is gt_e(G).

    lines 8–10

    uses Nat.sInf_mem

      have hmem := Nat.sInf_mem hne
      dsimp at hmem
      rcases hmem with ⟨T, hT_trans, hT_card⟩
  3. There exists a vertex geodesic transversal S with |S| ≤ |T|.

    Applying the lemma `exists_geodesic_transversal_of_edge_geodesic_transversal` to the minimal edge transversal T yields a vertex geodesic transversal S whose size is at most |T|.

    line 11

    uses exists_geodesic_transversal_of_edge_geodesic_transversal

      rcases exists_geodesic_transversal_of_edge_geodesic_transversal G T hT_trans with ⟨S, hS_trans, hS_le⟩
  4. The vertex geodesic transversal number gt(G) is at most |S|.

    Because S is a vertex geodesic transversal, |S| is a member of the set of cardinalities of vertex geodesic transversals. Unfolding the definition of gt(G) as the infimum of this set, `Nat.sInf_le` establishes that gt(G) ≤ |S|.

    lines 12–15

    uses Nat.sInf_le

      have hS_mem : S.card ∈ { k : ℕ | ∃ S' : Finset V, is_geodesic_transversal G S' ∧ S'.card = k } := by
        exact ⟨S, hS_trans, rfl⟩
      unfold geodesic_transversal_number
      have hle := Nat.sInf_le hS_mem
  5. The vertex geodesic transversal number is bounded above by the edge geodesic transversal number: gt(G) ≤ gt_e(G).

    Linear arithmetic finishes the proof by combining the inequalities gt(G) ≤ |S| and |S| ≤ |T| with the equality |T| = gt_e(G).

    line 16

      linarith
Nat.sInf_mem
Any nonempty set of natural numbers contains its infimum (minimum).
exists_geodesic_transversal_of_edge_geodesic_transversal
For any edge geodesic transversal T in a graph G, there exists a vertex geodesic transversal S whose cardinality is at most that of T.
Nat.sInf_le
The infimum of a set of natural numbers is less than or equal to any element in that set.

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

/-- For any connected simple graph G admitting a finite edge geodesic transversal, the vertex geodesic transversal number gt(G) is at most the edge geodesic transversal number gt_e(G). -/theorem geodesic_transversal_number_le_edge_geodesic_transversal_number {V : Type*} (G : SimpleGraph V) (hG : G.Connected) (hT : ∃ T : Finset (Sym2 V), is_edge_geodesic_transversal G T) : geodesic_transversal_number G ≤ edge_geodesic_transversal_number G := by  have _ := hG  unfold edge_geodesic_transversal_number  rcases hT with ⟨T0, hT0⟩  have hne : { k : ℕ | ∃ S : Finset (Sym2 V), is_edge_geodesic_transversal G S ∧ S.card = k }.Nonempty := by    exact ⟨T0.card, ⟨T0, hT0, rfl⟩⟩  have hmem := Nat.sInf_mem hne  dsimp at hmem  rcases hmem with ⟨T, hT_trans, hT_card⟩  rcases exists_geodesic_transversal_of_edge_geodesic_transversal G T hT_trans with ⟨S, hS_trans, hS_le⟩  have hS_mem : S.card ∈ { k : ℕ | ∃ S' : Finset V, is_geodesic_transversal G S' ∧ S'.card = k } := by    exact ⟨S, hS_trans, rfl⟩  unfold geodesic_transversal_number  have hle := Nat.sInf_le hS_mem  linarith
See it in the graphDiscuss this resultChallenge it