not_edge_geodesic_transversal_bound_of_edge_disjoint
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.
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).
uses
SimpleGraph.Walk.nil.reachableintro h let G1 : SimpleGraph PUnit := ⊥ have hG1 : G1.Connected := ⟨fun x y => by cases x; cases y; exact SimpleGraph.Walk.nil.reachable⟩
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.
uses
SimpleGraph.Walk.IsPath.nilhave 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⟩
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).
uses
Subsingleton.elimhave 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)
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.
have h_bound := h G1 hG1 1 h_disjNo 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.
uses
SimpleGraph.Walk.IsPath.nilhave 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
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.
uses
Set.mem_empty_iff_false,iff_false,Nat.sInf_emptyhave 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
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.
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.
- The informal text accompanying the theorem suggests a counterexample on an infinite star graph on ℕ. However, the formal Lean proof uses a simpler, degenerate counterexample: the single-vertex graph with no edges (G1 = ⊥ on PUnit).
- In Mathlib, the infimum of an empty set of natural numbers is defined to be 0 (Nat.sInf_empty). Because G1 admits no edge transversal, the set of transversal sizes is empty, so edge_geodesic_transversal_number G1 evaluates to 0 rather than being undefined or infinite.
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.
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