vertex_disjoint_routing_exists_zero
With p = 0 the disjoint-paths predicate holds, so it is not vacuously false.
Statement
theorem vertex_disjoint_routing_exists_zero {V : Type*} (Q : SimpleGraph V) : vertex_disjoint_routing_exists Q (fun i : Fin 0 => i.elim0) (fun i : Fin 0 => i.elim0)
- Source
- step towards weighted_spanning_tree_congestion_hardness_gap
- Verified
- 06 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- vertex_disjoint_routing_exists
DisjointPathsExist: there is a tuple of paths inQ, thei-th joinings_itot_i, whose supports are pairwise disjoint. - mixed_graph_is_valid_directed_triangleSanity check: the directed triangle is a mixed graph (no loops, no antiparallel arcs).
- vertex_disjoint_routing_exists
The proof, explained
The theorem verifies the base case where zero pairs of vertices are to be routed in a graph `Q`. Unfolding the definition of vertex-disjoint routing yields conditions quantified over the empty index type `Fin 0`. Because there are no pairs to route, the universal conditions are vacuously true, and simplification immediately closes the goal.
There exists a family of vertex-disjoint paths routing zero pairs of vertices in `Q`. automation
Unfolding the definition `vertex_disjoint_routing_exists` requires finding a family of paths `P` indexed by `Fin 0` such that each `P i` is a path and distinct paths are vertex-disjoint. Because `Fin 0` is the empty type, the universal quantifiers over `Fin 0` hold vacuously, and an empty family of paths exists trivially. The simplifier resolves all of these empty-domain conditions and closes the goal.
uses
mixed_graph_is_valid_directed_trianglevertex_disjoint_routing_exists Q (fun i : Fin 0 => i.elim0) (fun i : Fin 0 => i.elim0) := by first | exact mixed_graph_is_valid_directed_triangle | (apply mixed_graph_is_valid_directed_triangle <;> assumption) | (apply mixed_graph_is_valid_directed_triangle <;> simp_all) | simpa using mixed_graph_is_valid_directed_triangle | (simp only [vertex_disjoint_routing_exists] at *; first | exact mixed_graph_is_valid_directed_triangle | (apply mixed_graph_is_valid_directed_triangle <;> assumption) | (apply mixed_graph_is_valid_directed_triangle <;> simp_all) | simpa using mixed_graph_is_valid_directed_triangle)
mixed_graph_is_valid_directed_triangle- A directed 3-cycle on vertices `Fin 3` with the empty undirected graph forms a valid mixed graph.
- The proof in line 3 uses an automated fallback cascade (`first | ...`) that ends with `simpa using mixed_graph_is_valid_directed_triangle` after unfolding `vertex_disjoint_routing_exists`. The lemma `mixed_graph_is_valid_directed_triangle` is an artifact of the proof search script; its mathematical content is completely irrelevant to the proof, as the simplifier closes the goal purely because the index type `Fin 0` is empty.
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.
/-- Sanity witness for the disjoint-paths predicate: with no pairs there is nothing to route. -/theorem vertex_disjoint_routing_exists_zero {V : Type*} (Q : SimpleGraph V) : vertex_disjoint_routing_exists Q (fun i : Fin 0 => i.elim0) (fun i : Fin 0 => i.elim0) := by first | exact mixed_graph_is_valid_directed_triangle | (apply mixed_graph_is_valid_directed_triangle <;> assumption) | (apply mixed_graph_is_valid_directed_triangle <;> simp_all) | simpa using mixed_graph_is_valid_directed_triangle | (simp only [vertex_disjoint_routing_exists] at *; first | exact mixed_graph_is_valid_directed_triangle | (apply mixed_graph_is_valid_directed_triangle <;> assumption) | (apply mixed_graph_is_valid_directed_triangle <;> simp_all) | simpa using mixed_graph_is_valid_directed_triangle)