Alphabeta MathHow 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.
Matchings, saturated vertices, maximal and maximum matchings, perfect matchings and
Definition
Let be a finite simple graph. A matching is a set such that no two distinct edges of have a common endpoint. A vertex is -saturated when it is an endpoint of an edge of , and -exposed otherwise. The matching is perfect when every vertex is -saturated.
A matching is maximal when no strictly larger matching contains it, and is maximum when it has greatest cardinality among all matchings of . The matching number is The maximum exists because is finite and the empty set is a matching.
Remarks
- A maximal matching need not be maximum; the companion counterexample makes the distinction concrete.
Depends on
Used by
- The maximum matching from X has size |X|-max_S⊆ X(|S|-|N(S)|) Corollary
- Alternating and augmenting paths relative to a matching Definition
- 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 Lemma
- Maximal means inclusion-maximal; maximum means largest cardinality Remark
- Gallai's identity: ν(G)+ρ(G)=|V(G)| when G has no isolated vertex Theorem
- Hall's marriage theorem for a finite bipartite graph Theorem
- König's theorem: ν(G)=τ(G) for every finite bipartite graph Theorem
Dependency tree · two levels
9 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
- M. Goemans, Lecture notes on bipartite matching (standard reference, not scraped)