AFTD Auto-Formalizing Theoretical Domains

not_edge_geodesic_transversal_bound_of_edge_disjoint

theoremverifiedoriginal

The statement edge_geodesic_transversal_bound_of_edge_disjoint is false: The statement is false as formalized because it omits a finiteness hypothesis on G (the paper's Lemma 4 is about finite graphs; edge_geodesic_transversal_number is an infimum over *finite* edge sets Finset (Sym2 V), so for an infinite graph it degenerates to 0). COUNTEREXAMPLE. Let V = ℕ and let G be the star with center 0: Adj x y ↔ (x = 0 ∧ y ≠ 0) ∨ (x ≠ 0 ∧ y = 0). This is a connected simple graph. For distinct nonzero a, b, the 2-edge walk a → 0 → b has length 2 = G.dist a b, is a path, and satisfies both maximality distance conditions (the only neighbour of a other than b... precisely: any w adjacent to a is 0, and dist 0 b = 1 ≤ 2; any w adjacent to b is 0, and dist a 0 = 1 ≤ 2). So it is a maximal geodesic (this is is_maximal_geodesic). Hence G contains k = 1 mutually edge-disjoint maximal geodesics (any single one), and even k = 2. But no finite S : Finset (Sym2 ℕ) is an edge geodesic transversal: the edges s(n+1, 0), n ∈ ℕ, are pairwise distinct, so some a+1 ≠ 0 and b+1 ≠ 0 with s(a+1,0) ∉ S and s(b+1,0) ∉ S exist (S is finite, the family is infinite); then the maximal geodesic a+1 → 0 → b+1 has edges {s(a+1,0), s(0,b+1)}, neither in S (and s(0,b+1) ∉ S follows from s(b+1,0) ∉ S via Sym2.eq_swap). So is_edge_geodesic_transversal G S is false for every S, the set {k | ∃ S, is_edge_geodesic_transversal G S ∧ S.card = k} is empty, and therefore edge_geodesic_transversal_number G = sInf ∅ = 0. Yet k = 1 ≤ 0 is false. I verified all of these pieces in Lean (they elaborate with no errors, using only propext/Classical.choice/Quot.sound): the star graph is connected; starGraphAt/sga_connected; sga_max : is_maximal_geodesic for the 2-edge walk; sga_no_transversal : ¬ is_edge_geodesic_transversal (starGraphAt α c) S for every finite S (by the finite/infinite pigeonhole argument above); and consequently edge_geodesic_transversal_number (starGraphAt ℕ 0) = 0. Assembling them gives a proof of the negation — I ran out of budget before packaging it as one self-contained term, but every component was checked in Lean. Note the argument even shows k = 2 ≤ 0 fails; and for any infinite family the bound cannot hold.

Statement

theorem not_edge_geodesic_transversal_bound_of_edge_disjoint : ¬ (∀ {V : Type*} (G : SimpleGraph V) (hG : G.Connected)
    (k : ℕ)
    (h_disj : ∃ (u v : Fin k → V) (P : (i : Fin k) → G.Walk (u i) (v i)),
      (∀ i, is_maximal_geodesic (P i)) ∧
      ∀ (i j : Fin k), i ≠ j → ∀ e ∈ (P i).edges, e ∉ (P j).edges), k ≤ edge_geodesic_transversal_number G)
Related work
refutes `edge_geodesic_transversal_bound_of_edge_disjoint`
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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.
  • 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…
  • 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.

The proof, explained

The proof proceeds by contradiction by constructing a single-vertex counterexample. On the empty graph G1 with a single vertex, the trivial 0-length walk is a maximal geodesic that contains no edges. Taking k = 1 gives a family of mutually edge-disjoint maximal geodesics vacuously, which by the theorem would imply 1 ≤ edge_geodesic_transversal_number G1; but an edge transversal must intersect every maximal geodesic, which is impossible for an empty walk. Consequently, no transversal exists, the set of transversal sizes is empty, and by Mathlib's convention that sInf ∅ = 0 in ℕ, the transversal number is 0, giving the contradiction 1 ≤ 0.

  1. Assume the statement for contradiction and introduce the single-vertex graph G1, which is connected.

    We assume the universal claim holds in order to derive a contradiction (line 6). We define G1 to be the empty graph on the singleton type PUnit (line 7). Since PUnit has only one vertex, any two vertices are identical and connected by the empty walk SimpleGraph.Walk.nil, so G1 is connected (line 8).

    lines 6–8

    uses SimpleGraph.Walk.nil.reachable

      intro h
      let G1 : SimpleGraph PUnit := ⊥
      have hG1 : G1.Connected := ⟨fun x y => by cases x; cases y; exact SimpleGraph.Walk.nil.reachable⟩
  2. The empty walk on G1 is a maximal geodesic.

    Unfolding the definition of is_maximal_geodesic, the empty walk is a path and has length 0, which equals the distance between PUnit.unit and itself. Since G1 has no edges, no vertices are adjacent to PUnit.unit, so the maximality distance inequalities hold vacuously.

    lines 9–11

    uses SimpleGraph.Walk.IsPath.nil

      have h_max : is_maximal_geodesic (SimpleGraph.Walk.nil : G1.Walk PUnit.unit PUnit.unit) := by
        dsimp [is_maximal_geodesic]
        refine ⟨⟨SimpleGraph.Walk.IsPath.nil, by simp⟩, fun w hw => hw.elim, fun w hw => hw.elim⟩
  3. There exists a family of k = 1 mutually edge-disjoint maximal geodesics in G1.

    We instantiate the family of walks indexed by Fin 1 with the single walk SimpleGraph.Walk.nil, which was just shown to be a maximal geodesic. The edge-disjointness requirement for distinct indices i ≠ j in Fin 1 is vacuously true because Fin 1 has only one element (Subsingleton.elim i j gives i = j, contradicting i ≠ j).

    lines 12–18

    uses Subsingleton.elim

      have h_disj : ∃ (u v : Fin 1 → PUnit) (P : (i : Fin 1) → G1.Walk (u i) (v i)),
          (∀ i, is_maximal_geodesic (P i)) ∧
          ∀ (i j : Fin 1), i ≠ j → ∀ e ∈ (P i).edges, e ∉ (P j).edges := by
        refine ⟨fun _ => PUnit.unit, fun _ => PUnit.unit, fun _ => SimpleGraph.Walk.nil, fun _ => h_max, ?_⟩
        intro i j hij
        exfalso
        exact hij (Subsingleton.elim i j)
  4. The assumed bound specializes to 1 ≤ edge_geodesic_transversal_number G1.

    Applying the assumed universal hypothesis h to G1, its connectedness proof hG1, k = 1, and the witness h_disj yields the inequality 1 ≤ edge_geodesic_transversal_number G1.

    line 19

      have h_bound := h G1 hG1 1 h_disj
  5. No finite set of edges S is an edge geodesic transversal of G1.

    If S were an edge geodesic transversal, it would need to contain an edge from every maximal geodesic in G1, in particular from the empty walk SimpleGraph.Walk.nil. However, the empty walk has no edges (nil.edges is empty), making it impossible for S to intersect its edges.

    lines 20–27

    uses SimpleGraph.Walk.IsPath.nil

      have h_no_trans : ∀ S : Finset (Sym2 PUnit), ¬ is_edge_geodesic_transversal G1 S := by
        intro S hS
        dsimp [is_edge_geodesic_transversal] at hS
        obtain ⟨-, h2⟩ := hS
        have h_trans := h2 (SimpleGraph.Walk.nil : G1.Walk PUnit.unit PUnit.unit)
          ⟨SimpleGraph.Walk.IsPath.nil, by simp, fun w hw => hw.elim, fun w hw => hw.elim⟩
        rcases h_trans with ⟨e, -, he_nil⟩
        simp at he_nil
  6. edge_geodesic_transversal_number G1 = 0.

    The transversal number is defined as the infimum of the set of sizes of all edge geodesic transversals. Since no edge geodesic transversal exists, this set is empty. In ℕ, the infimum of the empty set is 0 by Nat.sInf_empty.

    lines 28–36

    uses Set.mem_empty_iff_false, iff_false, Nat.sInf_empty

      have h_zero : edge_geodesic_transversal_number G1 = 0 := by
        dsimp [edge_geodesic_transversal_number]
        have h_empty : { k : ℕ | ∃ S : Finset (Sym2 PUnit), is_edge_geodesic_transversal G1 S ∧ S.card = k } = ∅ := by
          ext k
          simp only [Set.mem_empty_iff_false, iff_false]
          rintro ⟨S, hS, -⟩
          exact h_no_trans S hS
        rw [h_empty]
        exact Nat.sInf_empty
  7. False (contradiction). automation

    Rewriting edge_geodesic_transversal_number G1 with 0 turns the inequality 1 ≤ edge_geodesic_transversal_number G1 into 1 ≤ 0, which is closed as an arithmetic contradiction by omega.

    lines 37–38

      rw [h_zero] at h_bound
      omega
SimpleGraph.Walk.nil.reachable
A vertex in a simple graph is reachable from itself via the empty walk.
SimpleGraph.Walk.IsPath.nil
The empty walk at any vertex is a path (it visits no vertex more than once).
Subsingleton.elim
Any two elements of a subsingleton type are equal.
Set.mem_empty_iff_false
An element x belongs to the empty set if and only if False.
iff_false
An equivalence p ↔ False simplifies to ¬p.
Nat.sInf_empty
The infimum (sInf) of the empty set of natural numbers is 0.

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

theorem not_edge_geodesic_transversal_bound_of_edge_disjoint : ¬ (∀ {V : Type*} (G : SimpleGraph V) (hG : G.Connected)    (k : ℕ)    (h_disj : ∃ (u v : Fin k → V) (P : (i : Fin k) → G.Walk (u i) (v i)),      (∀ i, is_maximal_geodesic (P i)) ∧      ∀ (i j : Fin k), i ≠ j → ∀ e ∈ (P i).edges, e ∉ (P j).edges), k ≤ edge_geodesic_transversal_number G) := by  intro h  let G1 : SimpleGraph PUnit := ⊥  have hG1 : G1.Connected := ⟨fun x y => by cases x; cases y; exact SimpleGraph.Walk.nil.reachable⟩  have h_max : is_maximal_geodesic (SimpleGraph.Walk.nil : G1.Walk PUnit.unit PUnit.unit) := by    dsimp [is_maximal_geodesic]    refine ⟨⟨SimpleGraph.Walk.IsPath.nil, by simp⟩, fun w hw => hw.elim, fun w hw => hw.elim⟩  have h_disj : ∃ (u v : Fin 1 → PUnit) (P : (i : Fin 1) → G1.Walk (u i) (v i)),      (∀ i, is_maximal_geodesic (P i)) ∧      ∀ (i j : Fin 1), i ≠ j → ∀ e ∈ (P i).edges, e ∉ (P j).edges := by    refine ⟨fun _ => PUnit.unit, fun _ => PUnit.unit, fun _ => SimpleGraph.Walk.nil, fun _ => h_max, ?_⟩    intro i j hij    exfalso    exact hij (Subsingleton.elim i j)  have h_bound := h G1 hG1 1 h_disj  have h_no_trans : ∀ S : Finset (Sym2 PUnit), ¬ is_edge_geodesic_transversal G1 S := by    intro S hS    dsimp [is_edge_geodesic_transversal] at hS    obtain ⟨-, h2⟩ := hS    have h_trans := h2 (SimpleGraph.Walk.nil : G1.Walk PUnit.unit PUnit.unit)      ⟨SimpleGraph.Walk.IsPath.nil, by simp, fun w hw => hw.elim, fun w hw => hw.elim⟩    rcases h_trans with ⟨e, -, he_nil⟩    simp at he_nil  have h_zero : edge_geodesic_transversal_number G1 = 0 := by    dsimp [edge_geodesic_transversal_number]    have h_empty : { k : ℕ | ∃ S : Finset (Sym2 PUnit), is_edge_geodesic_transversal G1 S ∧ S.card = k } = ∅ := by      ext k      simp only [Set.mem_empty_iff_false, iff_false]      rintro ⟨S, hS, -⟩      exact h_no_trans S hS    rw [h_empty]    exact Nat.sInf_empty  rw [h_zero] at h_bound  omega
See it in the graphDiscuss this resultChallenge it