Skip to main content
MathidiaMathematics Academy
Graph theory and networks
Lesson 48 of 75
Standard practice

Matchings

Objective. Apply augmenting paths and Hall's theorem.

  1. 1. Learn
  2. 2. Worked example
  3. 3. Practice
  4. 4. Feedback
  5. 5. Continue

Learn: the key idea

A matching in a graph is a set of edges with no shared vertices, and finding a maximum matching often uses augmenting paths: a path that alternates between edges outside and inside the matching, starting and ending at unmatched vertices. If no augmenting path exists, the matching is maximum (Berge's theorem). For bipartite graphs, Hall's theorem states a perfect matching saturating one side exists if and only if every subset S of that side has |N(S)| ≥ |S|, where N(S) is the set of neighbours of S. For example, if three workers can only collectively cover two distinct tasks between them, Hall's condition fails and no perfect matching of workers to tasks exists.

Worked example

Bipartite graph has workers {w1,w2,w3} and tasks {t1,t2}, where w1,w2,w3 can all only do task t1. Using Hall's theorem, determine if a matching saturating the workers exists.

1 … 2
Coordinate grid with the line 1 … 2
  1. 1Take S = {w1,w2,w3}, the whole worker side.
  2. 2Find N(S): the neighbourhood of all three workers is just {t1}, since none can do t2.
  3. 3Compare sizes: |N(S)| = 1 but |S| = 3, so |N(S)| < |S|.
  4. 4Hall's condition fails for this S, so no matching saturating all workers exists.

Answer: No, Hall's condition fails (|N(S)|=1 < |S|=3)

Concept mastery

Based on your past attempts at this lesson — the question types to practise again come first.

Complete a practice set to see your concept breakdown here.

Practice

Practice happens on its own screen, one question at a time. Answers stay hidden until you submit yours, and you can stop and pick up at the same question later.

Start practising

Common mistake. Students check Hall's condition only for individual vertices rather than all subsets S; a graph can satisfy the condition for singletons yet fail for a larger subset, so every subset must be tested, not just single vertices.

Your progress

Tick each step as you finish it. Your exact reading position is saved automatically, so Continue drops you back on the same line.

0 of 5 steps complete

Your place saves automatically as you read.

My dashboard