AFTD Auto-Formalizing Theoretical Domains

CarpoolForestEdgeSequence

def

A list of edges on Fin n is an oblivious forest edge sequence for online carpooling if all edges connect distinct vertices, no undirected edge appears more than once, and the simple graph formed by the edges is acyclic.

Statement

def CarpoolForestEdgeSequence (n : ℕ) (edges : List (Fin n × Fin n)) : Prop
Defined in
arXiv:2611.00388: Online carpooling against an oblivious adversary; OP-1106
Verified
08 Nov 2026
Axioms
none listed
Built on 1
  • ValidCarpoolEdgeSequenceA list of edges on n vertices is valid for online carpooling if every arriving edge connects two distinct vertices.
Used by 7

Read back from the Lean

Given a natural number n and a list edges of pairs (u, v) of vertices in Fin n, CarpoolForestEdgeSequence n edges asserts that: 1. Every edge e ∈ edges has distinct endpoints (e.1 ≠ e.2, i.e., no self-loops). 2. The list obtained by mapping each edge e in edges to the unordered pair s(e.1, e.2) contains no duplicate elements (List.Nodup). In particular, no undirected edge appears more than once, so neither duplicate directed edges nor pairs of antiparallel edges (u, v) and (v, u) are present. 3. The simple graph on Fin n whose edge set is {s(e.1, e.2) | e ∈ edges} is acyclic (i.e., a forest).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- A list of edges on Fin n is a carpool forest edge sequence if every edge connects distinct vertices, the undirected edges are pairwise distinct, and their union forms an acyclic simple graph (a forest). -/
def CarpoolForestEdgeSequence (n : ℕ) (edges : List (Fin n × Fin n)) : Prop := ValidCarpoolEdgeSequence n edges ∧
  (edges.map (fun e => s(e.1, e.2))).Nodup ∧
  (SimpleGraph.fromEdgeSet {s(e.1, e.2) | e ∈ edges}).IsAcyclic
See it in the graphDiscuss this resultChallenge it