Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — the vertices of PGP_GPG​ are precisely the branching vectors

Proved
OptimumBranchings.Polytope.vertices_eq_branching_vectors

by mikedeng1 · Sep 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

branchingsp2o-batch-p100ap2o-gran-per-chapterp2o-plan-paperp2o-v1polyhedral-combinatorics

Let GGG be a directed graph: finitely many nodes and edges, each edge directed from a rear end to a different front end, parallel edges allowed. Let PG⊆REP_G\subseteq\mathbb R^EPG​⊆RE be the polyhedron defined by (L1)(L_1)(L1​) xe≥0x_e\ge0xe​≥0, (L2)(L_2)(L2​) ∑e into vxe≤1\sum_{e\text{ into }v}x_e\le1∑e into v​xe​≤1 for every node vvv, and (L3)(L_3)(L3​) ∑e with both ends in Sxe≤∣S∣−1\sum_{e\text{ with both ends in }S}x_e\le|S|-1∑e with both ends in S​xe​≤∣S∣−1 for every set SSS of two or more nodes. Then

{x:x is a vertex of PG}={xB:B is a branching of G},\{x : x\text{ is a vertex of }P_G\}=\{x^B : B\text{ is a branching of }G\},{x:x is a vertex of PG​}={xB:B is a branching of G},

where xBx^BxB is the incidence vector of BBB and a vertex is a point of PGP_GPG​ that is the unique maximizer over PGP_GPG​ of some linear function.

This is Edmonds' description of the branching polytope: the linear system (L1)(L_1)(L1​)–(L3)(L_3)(L3​) has no fractional vertices, so optimum branchings can be found by linear programming and certified by duality.

Formalization Note The graph carries an explicit no-loop condition, as in the paper's definition; with a loop the theorem would be false.

Preamble
import Mathlib
import Definitions.Def_OptimumBranchings_Polytope_Graph
import Definitions.Def_OptimumBranchings_Polytope_BranchingPolyhedron
Formal statement
namespace OptimumBranchings.Polytope

/-- Edmonds (1967), Theorem 2, p. 235: the vertices of the polyhedron `P_G` are precisely the
vectors of the subsets of edges in `G` which comprise branchings. -/
theorem vertices_eq_branching_vectors {V E : Type*} [Fintype V] [DecidableEq V] [Fintype E]
    [DecidableEq E] (G : Graph V E) :
    {x : E → ℝ | IsVertex (branchingPolyhedron G) x} =
      {x : E → ℝ | ∃ B : Finset E, G.IsBranching B ∧ x = incidenceVector B} := by sorry

end OptimumBranchings.Polytope
Source
Edmonds, Optimum branchings, J. Res. Nat. Bur. Standards 71B (1967), p. 235, Theorem 2
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Fix a finite type of vertices VVV and a finite type of edges EEE, each with decidable equality, and a graph GGG on them. Here GGG is a term of Graph V E, a structure defined in an imported file that is not shown. Nothing in this declaration says how edges relate to vertices: whether an edge has a head and a tail, whether loops or parallel edges are allowed, or whether any condition links EEE to VVV. All of that depends on the unseen definition of Graph.

The statement is about points of RE\mathbb{R}^ERE, meaning real-valued functions x:E→Rx : E \to \mathbb{R}x:E→R that give each edge a real coordinate. It says that two subsets of RE\mathbb{R}^ERE are equal:

{ x∈RE  :  x is a vertex of PG }  =  { x∈RE  :  ∃ B⊆E finite, B is a branching of G and x=χB }.\{\, x \in \mathbb{R}^E \;:\; x \text{ is a vertex of } P_G \,\} \;=\; \{\, x \in \mathbb{R}^E \;:\; \exists\, B \subseteq E \text{ finite},\ B \text{ is a branching of } G \ \text{and}\ x = \chi^B \,\}.{x∈RE:x is a vertex of PG​}={x∈RE:∃B⊆E finite, B is a branching of G and x=χB}.

The symbols in this equation stand for the following:

  • PGP_GPG​ is branchingPolyhedron G. It is a subset of RE\mathbb{R}^ERE built from GGG by a definition in an imported file that is not shown. This declaration does not reveal which inequalities or constraints define it.
  • "xxx is a vertex of PGP_GPG​" is the predicate IsVertex applied to PGP_GPG​ and xxx. It is also defined in a file that is not shown, so its exact meaning is not visible here. It could be an extreme point, a point cut out by linearly independent tight constraints, or something else. The declaration also does not show whether being a vertex requires x∈PGx \in P_Gx∈PG​.
  • "BBB is a branching of GGG" is the predicate G.IsBranching B on a finite set BBB of edges. Its definition is not shown, so the acyclicity, in-degree or other conditions it imposes are not visible here.
  • χB\chi^BχB is incidenceVector B, a function E→RE \to \mathbb{R}E→R determined by the finite edge set BBB. Its definition is not shown. The name suggests the 0/10/10/1 indicator of BBB, but the declaration itself does not guarantee this.

The equality of sets means both of the following hold:

  1. Every vertex is an incidence vector of a branching. For every x∈REx \in \mathbb{R}^Ex∈RE, if xxx is a vertex of PGP_GPG​, then some finite edge set BBB is a branching of GGG and x=χBx = \chi^Bx=χB.
  2. Every incidence vector of a branching is a vertex. For every finite edge set BBB that is a branching of GGG, the vector χB\chi^BχB is a vertex of PGP_GPG​.

The docstring attributes the result to Edmonds (1967), Theorem 2, p. 235. It describes PGP_GPG​ as "the polyhedron" and the right-hand side as "vectors of the subsets of edges which comprise branchings". That wording is commentary; the formal content is only what is stated above. The claim holds for every choice of VVV, EEE, GGG and the decidable-equality instances, with no further hypotheses.

In degenerate cases, the statement asserts the following:

  • No edges. If EEE is empty, RE\mathbb{R}^ERE has exactly one point, the empty function, and the only finite edge set is B=∅B = \varnothingB=∅. The statement then says that this single point is a vertex of PGP_GPG​ exactly when ∅\varnothing∅ is a branching of GGG. Both sides are then either the whole one-point space or empty, depending on how the unseen definitions treat ∅\varnothing∅.
  • No vertices. If VVV is empty, whether EEE can be non-empty depends on the unseen definition of Graph. If edges must have endpoints in VVV, then EEE is empty too and the previous case applies.
  • One vertex. If VVV has one element, any edges present can only join that vertex to itself. Whether such edges exist, and whether a set containing them counts as a branching, depends on the unseen definitions.
  • Empty sides. Neither side is required to be non-empty. If no finite edge set satisfies IsBranching, the statement says PGP_GPG​ has no vertices in the sense of IsVertex, and the reverse also holds.
  • Default values. The declaration itself contains no division, natural-number subtraction, integral, supremum or extended-real arithmetic. Any such default-value behaviour could only come from inside the unseen definitions of branchingPolyhedron, IsVertex, IsBranching or incidenceVector.
Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Sep 27, 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