PropositionStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck 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 $xy$ ; a vertex cover $C_X\cup C_Y$ gives the cut $\{s\}\cup(X\setminus 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: $\nu(G)=\tau(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 $\nu(G)=\tau(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 · next 3 levels

Direct dependencies and their dependencies through the next three levels: 32 results over 16 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

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