carpool_forest_edge_sequence_nil
The empty list of edges is an oblivious forest edge sequence on Fin n.
Statement
theorem carpool_forest_edge_sequence_nil (n : ℕ) :
CarpoolForestEdgeSequence n []- Source
- arXiv:2611.00388: Online carpooling against an oblivious adversary; OP-1106
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- CarpoolForestEdgeSequenceA list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected…
Read back from the Lean
For every natural number $n$, the empty list of edges satisfies CarpoolForestEdgeSequence n [].
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 the empty list is a valid carpool forest edge sequence, we unfold the definition into three conditions: no self-loops, no duplicate edges, and acyclicity of the induced graph. The first two conditions hold trivially because the empty list has no elements. The third holds because the empty list yields an empty edge set, and the graph with no edges is acyclic.
It suffices to show that the graph formed by the empty list of edges is acyclic.
Unfolding the definition of a carpool forest edge sequence yields three conditions: every edge in the list must connect distinct vertices (no self-loops), the list must contain no duplicate undirected edges, and the graph formed by these edges must be acyclic. The first condition holds vacuously because the empty list has no elements. The second condition holds because the empty list has no duplicates (`List.nodup_nil`).
uses
List.nodup_nildsimp [CarpoolForestEdgeSequence, ValidCarpoolEdgeSequence] refine ⟨by simp, List.nodup_nil, ?_⟩
The set of undirected edges induced by the empty list is the empty set.
By extensionality, an undirected edge belongs to this set if and only if it arises from some element of the edge list. Because the empty list contains no elements, no such edge exists, so the set is empty.
have h_empty : {x | ∃ e ∈ ([] : List (Fin n × Fin n)), s(e.1, e.2) = x} = ∅ := by ext x; simp
The graph formed by the empty list is the empty graph ⊥, which is acyclic.
Rewriting the edge set with the fact that it is empty reduces the induced graph to `SimpleGraph.fromEdgeSet ∅`, which is the empty graph ⊥ (`SimpleGraph.fromEdgeSet_empty`). The empty graph has no edges and is therefore acyclic (`SimpleGraph.isAcyclic_bot`).
uses
SimpleGraph.fromEdgeSet_empty,SimpleGraph.isAcyclic_botrw [h_empty, SimpleGraph.fromEdgeSet_empty] exact SimpleGraph.isAcyclic_bot
List.nodup_nil- An empty list has no duplicate elements.
SimpleGraph.fromEdgeSet_empty- The simple graph constructed from the empty set of edges is the empty graph ⊥ (the graph with no edges).
SimpleGraph.isAcyclic_bot- The empty graph ⊥ has no cycles.
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.
/-- The empty edge sequence is a valid carpool forest edge sequence. -/theorem carpool_forest_edge_sequence_nil (n : ℕ) : CarpoolForestEdgeSequence n [] := by dsimp [CarpoolForestEdgeSequence, ValidCarpoolEdgeSequence] refine ⟨by simp, List.nodup_nil, ?_⟩ have h_empty : {x | ∃ e ∈ ([] : List (Fin n × Fin n)), s(e.1, e.2) = x} = ∅ := by ext x; simp rw [h_empty, SimpleGraph.fromEdgeSet_empty] exact SimpleGraph.isAcyclic_bot