---
title: "Matchings and Hall's Theorem"
description: "Decide when every element of one side can be paired off, and prove that the obvious obstruction is the only one."
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-09-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

Decide when every element of one side can be paired off, and prove that the obvious obstruction is the only one.

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

Split the world into two sides with edges only across: applicants to jobs, students to projects. A matching pairs left vertices to distinct right neighbours, and a full one covers every left vertex. The Hall condition checks every group of left vertices for enough collective neighbours. With 4 applicants there are 15 nonempty groups to examine.

**Example.** One tight group decides everything. If some group jointly suits too few jobs, Hall fails and no full pairing exists: that group is the blocking set. With A and B both suiting only X, the pair A and B shares a single job and the deal is dead. When Hall holds for every group, a full pairing is guaranteed, which is why the condition is sufficient and not merely necessary.

To build the pairing, start from an unmatched applicant and walk along unused then used edges. On reaching an unmatched job, flip the path and gain one pair. Repeat until nobody is left or no such path exists. Failure certifies a Hall violator: the fenced in group you could reach.

**Tip.** Test groups, never single people. A lone applicant can look fine while a pair quietly shares one job. Always merge the suits of the whole group before you count.

**Recap.** Check every group for enough jobs, then pair off or name the blocking group.

## Practice

17 questions on this page, each with its working shown.

## Needs first

- [Graph Colouring and Planarity](https://lightmysky.com/learn/mathematics/graph-colouring-and-planarity-mt_6xy6UPBppw)
- [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)