Hall’s marriage theorem

Hall定理

Combinatorics · Undergraduate · Mathematics Resources editorial compilation (AI-assisted)

Other names / variants: Hall's theorem · marriage theorem

Translation evidence: Literature usage

Meaning in context

A finite bipartite graph with parts L and R has a matching saturating L if and only if every S ⊆ L has at least |S| distinct neighbors in R.

有限二部图的两个部分为 L、R；存在饱和 L 的匹配，当且仅当每个 S⊆L 在 R 中的邻集大小至少为 |S|。

Example

If $N(a)=\{1\}$ and $N(b)=\{1\}$, the set $\{a,b\}$ violates Hall’s condition.

Usage and distinctions

The theorem saturates the designated part; calling the result perfect additionally requires all opposite-side vertices to be saturated.

Read the encyclopedia explanation

Recommended reading in this subject · Preparation & skip guidance

Definition sources

1. Keller and Trotter — Applied Combinatorics (2016)Section 14.2, Theorem 14.7 Hall’s Theorem · Checked 2026-10-14

Translation sources

1. 南京大学计算机科学与技术系 — 二部图中的匹配，离散数学课程组slide 9 / PDF p.9「Hall定理(1935, Marriage Theorem)」 · Checked 2026-10-14

Original encyclopedia and terminology content: CC BY-SA 4.0. Contribute or report a correction.