--- title: "Matchings and Hall's Theorem" description: "For a finite bipartite graph, decide whether every left vertex can be matched to a different right neighbour, and prove Hall's condition is necessary and sufficient." canonical: https://lightmysky.com/learn/mathematics/matchings-and-halls-theorem-mt_hkWslW5b5U source: https://lightmysky.com/learn/mathematics/matchings-and-halls-theorem-mt_hkWslW5b5U.md retrieved: 2026-11-12 --- > **Agent view.** This is the Markdown twin of the page, for tools and assistants. > When to use this site, and the call that answers each job: https://lightmysky.com/agent-instructions.md > API description (OpenAPI 3.1): https://lightmysky.com/openapi.json · Authentication: https://lightmysky.com/auth.md > Pricing: https://lightmysky.com/pricing.md · Catalog: https://lightmysky.com/llms.txt · Full catalog: https://lightmysky.com/llms-full.txt > Every machine-readable file on this domain: https://lightmysky.com/.well-known/ai-catalog.json > Ask for Markdown with `Accept: text/markdown`, a `.md` address, or `?mode=agent`. # Matchings and Hall's Theorem For a finite bipartite graph, decide whether every left vertex can be matched to a different right neighbour, and prove Hall's condition is necessary and sufficient. Subject: Mathematics · Area: Discrete Mathematics · Ages 21 to 22 Page: https://lightmysky.com/learn/mathematics/matchings-and-halls-theorem-mt_hkWslW5b5U ## Ready when they can - State Hall's condition and check it on a small bipartite graph - Prove that Hall's condition is sufficient, not merely necessary - Recast an assignment problem as a matching and read off what blocks a full pairing ## Lesson: Pair everyone or find the blocker In a finite bipartite graph, the vertex sets L and R have edges only between the sides. A matching is a set of edges with no shared endpoint. A left-covering matching gives every vertex in L a different neighbour in R. It may leave right vertices unused. A perfect matching covers both sides. Equal side sizes are necessary for a perfect matching, but do not guarantee one. For S contained in L, N(S) contains every right vertex adjacent to at least one member of S. Merge the neighbour lists and count each job once. Hall's condition is |N(S)| >= |S| for every S contained in L. Bars around a set name mean its number of members. The empty set passes because 0 >= 0. Hall's theorem says this condition is necessary and sufficient for a left-covering matching. Hall's condition is necessary: a matching covering the left side assigns |S| different neighbours to every group S. If |N(S)| < |S|, that group blocks such a matching. For example, two applicants who both suit only one job each have a neighbour, but their pair has too few. Checking only individual applicants misses this obstruction. More applicants than available jobs also blocks a full assignment. Each left vertex is either included or omitted, giving 2^n subsets for n left vertices. A full Hall check may omit the empty subset because it always passes. That leaves 2^n - 1 nonempty groups. Check singleton groups as well as larger ones. To enlarge a matching, start from an unmatched left vertex. Search along unused edges left to right and matched edges right to left. An augmenting path ends at an unmatched right vertex and repeats no vertices. Flip it by removing its matched edges and adding its unused edges. This gains one pair. A matching with no edge you can add may still grow by rerouting. Choosing any suitable pair and deleting its endpoints need not preserve Hall's condition. *(drawing: Edges: F-U, D-U, D-V, E-V, E-W. Start with D-U and E-V. Flip this path to get F-U, D-V and E-W.)* If an exhaustive search from one unmatched left vertex reaches no unmatched right vertex, let S and T be the reached left and right sets. Every neighbour of S is reached: unused edges are explored, while each reached matched left vertex's partner was already reached. Thus N(S)=T. Each vertex in T is matched, and its partner is reached. Those partners are exactly S except the unmatched start. Therefore |S|=|T|+1, so S violates Hall. To prove sufficiency, assume Hall's condition and choose a largest matching, which exists because the graph is finite. If a left vertex is unmatched, search from it. An augmenting path would increase the matching, contradicting its size. Without such a path, the search gives N(S)=T and |S|=|T|+1, contradicting Hall's condition. Both alternatives are impossible, so the largest matching covers the left side. A tight set S has exactly |S| neighbours. In a left-covering matching, S uses all those neighbours, so vertices outside S need partners outside N(S). If a group has s members and only t neighbours, with s>t, at least s-t members stay unmatched. Any matching then has at most |L|-(s-t) pairs. Prove a claimed maximum by giving an upper bound and a matching attaining it. **Recap.** Check every group for enough jobs, then pair off or name the blocking group. *This lesson, its questions, flashcards and worked solutions were written for this dataset.* ## Practice 17 questions on this page, each with its working shown. ## Needs first - [Network Flow and the Max-Flow Min-Cut Theorem](https://lightmysky.com/learn/computing/network-flow-and-the-max-flow-min-cut-theorem-mt_momRV9lK1n) ## Optional connections - [Graph Colouring and Planarity](https://lightmysky.com/learn/mathematics/graph-colouring-and-planarity-mt_6xy6UPBppw)