Theorem 2 — the vertices of are precisely the branching vectors
ProvedOptimumBranchings.Polytope.vertices_eq_branching_vectorsLet 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 be the polyhedron defined by , for every node , and for every set of two or more nodes. Then
where is the incidence vector of and a vertex is a point of that is the unique maximizer over of some linear function.
This is Edmonds' description of the branching polytope: the linear system – 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.
import Mathlib import Definitions.Def_OptimumBranchings_Polytope_Graph import Definitions.Def_OptimumBranchings_Polytope_BranchingPolyhedron
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
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Fix a finite type of vertices and a finite type of edges , each with decidable equality, and a graph on them. Here 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 to . All of that depends on the unseen definition of Graph.
The statement is about points of , meaning real-valued functions that give each edge a real coordinate. It says that two subsets of are equal:
The symbols in this equation stand for the following:
- is
branchingPolyhedron G. It is a subset of built from by a definition in an imported file that is not shown. This declaration does not reveal which inequalities or constraints define it. - " is a vertex of " is the predicate
IsVertexapplied to and . 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 . - " is a branching of " is the predicate
G.IsBranching Bon a finite set of edges. Its definition is not shown, so the acyclicity, in-degree or other conditions it imposes are not visible here. - is
incidenceVector B, a function determined by the finite edge set . Its definition is not shown. The name suggests the indicator of , but the declaration itself does not guarantee this.
The equality of sets means both of the following hold:
- Every vertex is an incidence vector of a branching. For every , if is a vertex of , then some finite edge set is a branching of and .
- Every incidence vector of a branching is a vertex. For every finite edge set that is a branching of , the vector is a vertex of .
The docstring attributes the result to Edmonds (1967), Theorem 2, p. 235. It describes 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 , , and the decidable-equality instances, with no further hypotheses.
In degenerate cases, the statement asserts the following:
- No edges. If is empty, has exactly one point, the empty function, and the only finite edge set is . The statement then says that this single point is a vertex of exactly when is a branching of . Both sides are then either the whole one-point space or empty, depending on how the unseen definitions treat .
- No vertices. If is empty, whether can be non-empty depends on the unseen definition of
Graph. If edges must have endpoints in , then is empty too and the previous case applies. - One vertex. If 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 has no vertices in the sense ofIsVertex, 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,IsBranchingorincidenceVector.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.