Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

DFS: correctness and uniform linear running time

Proved
CLRS.DFS.correctness_and_running_time

by Chutong · Oct 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgorithmsclrsgraph-theoryrunning-timetextbook

There is one positive natural constant C such that every heap representing a finite directed graph admits a terminating call to the displayed identity-order DFS with fresh outputs, preserved caller storage, the full forest/timestamp/white-path contract, and

T≤C(1+n+m).T\le C(1+n+m).T≤C(1+n+m).

C is independent of all graph data, heaps, and initial clocks. The result lists vertices in increasing finish time and labels predecessor trees, not SCCs. Empty graphs are included. No algorithm proof is supplied.

Preamble
import Definitions.Def_CLRS_DFS_Program

set_option autoImplicit false

open Algo2LeanGenerated CLRS.GraphTraversal CLRS.DFS
Formal statement
theorem CLRS.DFS.correctness_and_running_time :
    ∃ C : Nat, 0 < C ∧
      ∀ (before : Heap) (graph : ObjectRef) (g : Graph),
        GraphRep before graph g →
        ∃ (after : Heap) (result : ObjectRef),
          Algo.dfs.dfs.Call before graph after result ∧
          Post before after result g (fun i : Int => i) ∧
          work before after ≤ C * (1 + g.size + edgeCount g) := by
  sorry
Source
CLRS, Introduction to Algorithms, fourth edition (MIT Press, 2022), Chapter 20, §20.3. https://mitpress.mit.edu/9780262046305/introduction-to-algorithms/ ; new arrays-of-arrays implementation compiled with Algo2Lean v0.1.4, https://www.algo2lean.com/versions/v0.1.4/ . Source filenames and full code are in the mission description.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex, independent fresh-context agent)

There exists one natural-number constant C>0C>0C>0 such that, for every initial heap HHH, natural-number graph-object reference aaa, and graph ggg represented by aaa in HHH, there exist a final heap H′H'H′ and object reference rrr satisfying the completed-call relation for dfs on aaa, the postcondition below with q(i)=iq(i)=iq(i)=i for every integer iii, and W≤C(1+n+m)W\le C(1+n+m)W≤C(1+n+m). The constant is uniform over all heaps, input references, graphs, and initial counter values; no numeric value or lower bound on work is specified. Here a graph ggg consists of a natural number nnn and, for each natural number uuu, a finite ordered list N(u)N(u)N(u) of natural numbers, with every entry of N(u)N(u)N(u) less than nnn whenever u<nu<nu<n; its vertices are the integers 0≤v<n0\le v<n0≤v<n, an edge u→vu\to vu→v means that both endpoints are vertices and vvv occurs in N(u)N(u)N(u), and m=∑u=0n−1∣N(u)∣m=\sum_{u=0}^{n-1}|N(u)|m=∑u=0n−1​∣N(u)∣ counts occurrences, including parallel edges and self-loops. No symmetry is required, and rows at indices u≥nu\ge nu≥n are unrestricted. The representation hypothesis means that the initial heap HHH contains the allocated graph object aaa with class tag graph_input.UnweightedGraph, integer size field nnn, an allocated collection of type Seq[Int] in its adjacency field, and an allocated integer sequence in its degree field; for each 0≤u<n0\le u<n0≤u<n, the degree entry equals ∣N(u)∣|N(u)|∣N(u)∣, the adjacency collection entry decodes to an allocated integer-sequence reference, and that row's entries 0≤j<∣N(u)∣0\le j<|N(u)|0≤j<∣N(u)∣ equal the corresponding ordered entries of N(u)N(u)N(u). Integer sequences are total functions Z→Z\mathbb Z\to\mathbb ZZ→Z; only the stated prefixes are constrained, and allocated input sequences, including rows and the degree sequence, may share identities. Heap reference identities are natural numbers in separate sequence, object, and collection spaces, and allocation means that the identity is smaller than that space's allocation counter. The completed-call relation requires that the graph reference is an allocated object of the graph class (and, for ordered traversal, that the order sequence is allocated), and, for every finite stack of suspended caller continuations, the existence of a finite sequence of the program's individual transitions from the entry frame on that stack to the same final heap and tagged result returned to that stack: the empty stack yields a completed top-level configuration, and a nonempty stack applies its first continuation to the result and retains the remaining stack. Thus the assertion supplies a terminating execution for every such stack, with H′H'H′ and rrr chosen independently of the stack; it is not merely a conditional assertion about a supplied successful execution. The resulting heap H′H'H′ contains an allocated object rrr of class dfs.DFSResult whose identity is at least the initial object-allocation counter, and its six fields color, parent, discover, finish, order, and component point to pairwise distinct allocated integer sequences, each with identity at least the initial sequence-allocation counter. Write their contents as c,p,d,f,o,bc,p,d,f,o,bc,p,d,f,o,b. Every initially allocated sequence retains its contents at every integer index, every initially allocated object and collection retains its entire stored value, all three allocation counters do not decrease, the named heap counter graph_work does not decrease, and all other named heap counters are unchanged. The result's separate integer fields clock and finished equal 2n2n2n and nnn, and c(v)=2c(v)=2c(v)=2 for every vertex. There is a natural number k≤nk\le nk≤n such that the result's components field equals kkk, and the following conditions hold. Each vertex vvv has p(v)=−1p(v)=-1p(v)=−1 or an edge p(v)→vp(v)\to vp(v)→v; 1≤d(v)<f(v)≤2n1\le d(v)<f(v)\le2n1≤d(v)<f(v)≤2n; discovery times are pairwise distinct, finishing times are pairwise distinct, and d(u)≠f(v)d(u)\ne f(v)d(u)=f(v) for every pair of vertices. For every two vertices u,vu,vu,v, either f(u)<d(v)f(u)<d(v)f(u)<d(v), or f(v)<d(u)f(v)<d(u)f(v)<d(u), or d(u)≤d(v)d(u)\le d(v)d(u)≤d(v) and f(v)≤f(u)f(v)\le f(u)f(v)≤f(u), or d(v)≤d(u)d(v)\le d(u)d(v)≤d(u) and f(u)≤f(v)f(u)\le f(v)f(u)≤f(v). Define A(u,v)A(u,v)A(u,v) to mean that there is a finite sequence of vertices starting at uuu and ending at vvv, possibly of length zero, such that each successive vertex yyy has parent equal to its predecessor; thus every vertex is its own ancestor. For vertices u,vu,vu,v, A(u,v)A(u,v)A(u,v) holds if and only if d(u)≤d(v)d(u)\le d(v)d(u)≤d(v) and f(v)≤f(u)f(v)\le f(u)f(v)≤f(u), and also if and only if there is a directed graph walk from uuu to vvv, possibly of length zero, all of whose vertices www satisfy d(u)≤d(w)d(u)\le d(w)d(u)≤d(w). With the input-priority sequence denoted by qqq, for every natural i<ni<ni<n with p(q(i))=−1p(q(i))=-1p(q(i))=−1, every natural j<ij<ij<i satisfies f(q(j))<d(q(i))f(q(j))<d(q(i))f(q(j))<d(q(i)). The prefix o(0),…,o(n−1)o(0),\ldots,o(n-1)o(0),…,o(n−1) is a permutation of the vertices and satisfies f(o(i))<f(o(j))f(o(i))<f(o(j))f(o(i))<f(o(j)) whenever 0≤i<j<n0\le i<j<n0≤i<j<n. Every vertex has 0≤b(v)<k0\le b(v)<k0≤b(v)<k, every natural label ℓ<k\ell<kℓ<k is attained by a vertex, and b(u)=b(v)b(u)=b(v)b(u)=b(v) holds exactly when there is a vertex zzz with p(z)=−1p(z)=-1p(z)=−1, A(z,u)A(z,u)A(z,u), and A(z,v)A(z,v)A(z,v). For roots u,vu,vu,v satisfying p(u)=p(v)=−1p(u)=p(v)=-1p(u)=p(v)=−1, b(u)<b(v)b(u)<b(v)b(u)<b(v) holds if and only if d(u)<d(v)d(u)<d(v)d(u)<d(v). These labels describe parent trees; no equivalence with strong connectivity is asserted. The postcondition imposes no contents on the six output sequences outside their vertex prefixes and does not specify the exact total amount of new storage. The work measure WWW is the natural-number difference between the final and initial values of the named heap counter graph_work, using subtraction truncated at zero; the preservation condition prevents a decrease here. It counts the explicit unit tick transitions, including those in nested calls, rather than all individual transitions or machine operations; the initial counters are arbitrary and are not reset. No input-priority array is supplied by the caller. The case n=0n=0n=0 is included: the result has k=0k=0k=0 and both integer event counters zero, and W≤CW\le CW≤C. The proof is left as an unproved goal.

Human review
  • Endorsed by Shuze Chen · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Chutong · Oct 15, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me