PropositionStatement: AI-adaptedProof: AI-adaptedprecheck passaudited 2026-08-02

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The unit network for a bipartite graph identifies integral flows with matchings and finite cuts with vertex covers

Statement

For a finite bipartite graph with parts $(X, Y)$ , give the arcs $s \to x$ , each graph edge $x \to y$ , and $y \to t$ unit capacity. Integral flow paths correspond to matching edges $x y$ ; a vertex cover $C_{X} \cup C_{Y}$ gives the cut ${s} \cup (X ∖ C_{X}) \cup C_{Y}$ of the same size. Consequently the maximum-flow/minimum-cut equality agrees with the matching/cover equality, and a flow of value $∣ X ∣$ agrees with Hall's saturating matching criterion.

Facts & Assumptions

Given: The displayed unit network of a finite bipartite graph $(X, Y)$ .

[L1]

Integral Ford--Fulkerson gives equal maximum flow and minimum cut values (Ford-Fulkerson terminates for finite integer capacities and proves max-flow min-cut with an integral maximum flow).

[L2]

A unit-capacity integral flow decomposes into arc-disjoint source-sink paths (An integral flow decomposes into source-sink path flows and directed cycle flows; unit capacities make the paths arc-disjoint).

[L3]

In a finite bipartite graph, matching and minimum vertex-cover sizes agree (König's theorem: $ν (G) = τ (G)$ for every finite bipartite graph).

[L4]

Hall's condition is equivalent to a matching saturating the left part (Hall's marriage theorem for a finite bipartite graph).

Proof

technique · direct

1.1

By [L2], each unit source-sink path has the form $s, x, y, t$ , and arc-disjointness makes its middle edges a matching; conversely a matching gives these unit paths.

1.2

A vertex cover $C_{X} \cup C_{Y}$ yields the stated cut: no $x \to y$ arc crosses it, and its only cut arcs are the $∣ C_{X} ∣$ source arcs and $∣ C_{Y} ∣$ sink arcs.

given

1.3

Thus [L1] makes maximum flow equal minimum cut, and [L3] identifies their common value with $ν (G) = τ (G)$ .

L1L3

2.1

A flow of value $∣ X ∣$ uses every unit arc out of $s$ , so step 1.1 makes a matching saturating $X$ ; [L4] gives the equivalent Hall condition.

3.1

The path, cut, matching, cover, and Hall correspondences in steps 1.1--2.1 prove the proposition.

step 1.1step 1.2step 1.3step 2.1∎

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

15 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

MIT OCW 18.200, Principles of Discrete Applied Mathematics (standard reference, not scraped)