Graphs · step 14 of 14

Matchings & Hall’s marriage theorem

A matching is a set of edges with no shared endpoints; a perfect matching covers every vertex. For bipartite graphs Hall’s theorem gives an exact criterion: a matching saturating one side exists iff every subset S of that side has |N(S)| ≥ |S|. Finding a violating set is therefore a complete, checkable proof that no such matching exists.

Practise matchings & hall’s marriage theorem free → All Graphs subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

State Hall’s conditionFor every subset S of the left part, the neighbourhood N(S) must be at least as large as S.
Hunt for a violating setLook for several left vertices whose neighbourhoods all sit inside a small set — that is the bottleneck.
Build a matching greedily, then augmentTake any matching, then find an augmenting path — one alternating unmatched/matched edges between two unmatched vertices — and flip it.
Certify optimalityBy König’s theorem, the maximum matching size equals the minimum vertex cover size in a bipartite graph. Exhibiting a cover of equal size proves the matching is maximum.

Worked example

Four applicants A, B, C, D apply for jobs. A, B and C are each qualified only for jobs 1 and 2; D is qualified for job 3. Can all four be assigned?

Take S = {A, B, C}, so |S| = 3.
N(S) = {1, 2}, so |N(S)| = 2.
2 < 3, so Hall’s condition fails.
The three applicants compete for only two jobs.

Answer. No — Hall’s condition fails on {A,B,C}, so no assignment covers all four applicants. A maximum matching has size 3.

Where marks get dropped

These are the specific errors that cost credit on matchings & hall’s marriage theorem questions — QED's rubric penalises each of them separately.

Checking Hall’s condition only on single vertices. The condition must hold for EVERY subset, and violations typically involve two or three vertices.
Computing N(S) as the neighbours of one element. It is the union of the neighbourhoods across all of S.
Assuming a maximal matching is maximum. A matching that cannot be extended may still be improvable via an augmenting path.

Practise this until it is automatic

Unlimited fresh questions

QED generates new matchings & hall’s marriage theorem problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Graphs mastery is tracked so you know when this is exam-ready.

Matchings & Hall’s marriage theorem — frequently asked questions

What is König’s theorem?

In a bipartite graph the maximum matching size equals the minimum vertex cover size. It is the min-max duality that makes bipartite matching efficiently solvable.

How is a maximum matching computed?

By repeatedly finding augmenting paths — the Hopcroft–Karp algorithm does this in O(E√V), which is fast enough for large instances.

Does Hall’s theorem apply to non-bipartite graphs?

No. The analogue there is Tutte’s theorem, whose condition counts odd components after deleting a vertex set.

The rest of Graphs

Terminology, connectivity, trees, paths and cycles. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make matchings & hall’s marriage theorem exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →