AFTD Auto-Formalizing Theoretical Domains

vertex_disjoint_routing_exists_zero

theoremverified

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

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.

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

    line 3

    uses mixed_graph_is_valid_directed_triangle

        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)
mixed_graph_is_valid_directed_triangle
A directed 3-cycle on vertices `Fin 3` with the empty undirected graph forms a valid mixed graph.

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

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