Alphabeta Math

Matchings, Covers, Menger and Network Flows

About this page
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.

✓ 19 results · all verified · 0 also independently AI-judged
Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 19 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.
1 · Prerequisites
Abstract Algebra
Combinatorics
Real Analysis
Set Theory
2 · Logical flowchart

3 · Items

Definition

Matchings, saturated vertices, maximal and maximum matchings, perfect matchings and ν(G)

Remark

Maximal means inclusion-maximal; maximum means largest cardinality

Definition

Vertex covers, edge covers and the covering numbers τ(G) and ρ(G)

Definition

Alternating and augmenting paths relative to a matching

Lemma

Switching along an augmenting path increases a matching by one edge

Lemma

The symmetric difference of two matchings is a disjoint union of alternating paths and even cycles

Theorem

Berge's theorem: a matching is maximum if and only if it has no augmenting path

Definition

Bipartite neighbourhoods, Hall's condition and systems of distinct representatives

Lemma

Hall's condition passes to the strict and tight induction subinstances

Theorem

Hall's marriage theorem for a finite bipartite graph

Corollary

A finite family has an SDR if and only if every subfamily has a union at least as large as its index set

Corollary

The maximum matching from X has size |X|-max_S⊆ X(|S|-|N(S)|)

Lemma

Alternating reachability from unmatched left vertices produces a vertex cover of the same size as a maximum matching

Theorem

König's theorem: ν(G)=τ(G) for every finite bipartite graph

Theorem

Gallai's identity: ν(G)+ρ(G)=|V(G)| when G has no isolated vertex

Definition

Finite integral networks, feasible flows, values, cuts and residual networks

Lemma

A flow's value is its net flow across every source-sink cut and never exceeds the cut capacity

Lemma

Augmenting by the residual bottleneck preserves feasibility and increases the flow value

Lemma

If the residual network has no source-sink path, its reachable set gives a cut whose capacity equals the flow value

Theorem

Ford-Fulkerson terminates for finite integer capacities and proves max-flow min-cut with an integral maximum flow

Lemma

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

Proposition

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

Definition

Arc-disjoint, edge-disjoint and internally vertex-disjoint path families and their local separators

Theorem

Menger's theorem: the finite directed and undirected arc, edge and nonadjacent-vertex forms

Corollary

A finite graph on at least k+1 vertices is k-connected if and only if every two vertices have k internally disjoint paths

Lemma

Every three-connected simple graph with more than four vertices has an edge whose simple contraction remains three-connected

Sources