Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 3.5.4 — a forest has a source with at most one successor or a sink with exactly one predecessor

Proved
ProjSchedTW.NetPresentValue.forest_source_or_sink

by mikedeng1 · Oct 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

forestgraph-theoryp2o-batch-b23bp2o-gran-per-chapterp2o-plan-bookp2o-v1

Let AAA be the arc set of a directed forest on a finite nonempty node set VVV: there are no loops and no pair of opposite arcs, and the underlying undirected graph has no cycle (so every weakly connected component is a tree). A source is a node without predecessors and a sink a node without successors. Then there is a node vvv such that

v is a source with at most one successororv is a sink with exactly one predecessor.v\ \text{is a source with at most one successor}\quad\text{or}\quad v\ \text{is a sink with exactly one predecessor}.v is a source with at most one successororv is a sink with exactly one predecessor.

In the book this property of forests (Berge 1976) is what makes the steepest descent direction problem for the net present value objective solvable by repeatedly removing such a node from the spanning forest.

Preamble
import Mathlib
Formal statement
namespace ProjSchedTW.NetPresentValue

/-- Proposition 3.5.4 (p. 252). A forest (a directed graph each of whose weakly connected
components is a tree, §3.2, p. 216) on a finite nonempty node set `V`, given by its arc set `A`
(no loops, no pair of opposite arcs, underlying undirected graph acyclic), possesses a source (no
predecessor) with at most one successor or a sink (no successor) with exactly one predecessor. -/
theorem forest_source_or_sink {V : Type} [Fintype V] [DecidableEq V] [Nonempty V]
    (A : Finset (V × V)) (hasymm : ∀ a b : V, (a, b) ∈ A → (b, a) ∉ A)
    (hacyc : (SimpleGraph.fromRel (fun a b => (a, b) ∈ A)).IsAcyclic) :
    ∃ v : V,
      ((∀ u, (u, v) ∉ A) ∧ (A.filter (fun e => e.1 = v)).card ≤ 1) ∨
      ((∀ w, (v, w) ∉ A) ∧ (A.filter (fun e => e.2 = v)).card = 1) := by sorry

end ProjSchedTW.NetPresentValue
Source
Neumann, Schwindt & Zimmermann, Project Scheduling with Time Windows and Scarce Resources, 2nd ed., Springer 2003, p. 252, Proposition 3.5.4; definition of tree and forest p. 216
Human review
  • Endorsed by Shuze Chen · Oct 5, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 5, 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