Find a matching or a Hall obstruction

Try

Three tasks need three distinct workers, and each task lists eligible workers. Having at least one eligible worker per task does not suffice: all three tasks might share only two workers. Hall’s theorem detects exactly these collective bottlenecks. The relevant quantity is the union of neighbors of every subset of tasks, not merely the individual degrees or the total number of edges.

Predict

Predict what a failed assignment should return. A list of unsuccessful greedy choices is not an impossibility proof, because a different assignment may work. A subset S of tasks with fewer than size (S) eligible workers is a short certificate: no assignment can give those tasks distinct partners. Conversely, Hall’s theorem proves that if no such subset exists in a finite bipartite graph, all left vertices can be matched.

Experiment

Live experiment: find a matching and a certificate

Three people a, b, c each need a different task 1, 2, 3. An edge means that assignment is permitted. Predict whether all three can be assigned before changing the graph. Labels and checkboxes carry the same information as the drawing.

Starting graph Overlapping choicesThree separate assignmentsOne shared taskEvery assignmentNo assignmentsInspect left subset S {}{a}{b}{a, b}{c}{a, c}{b, c}{a, b, c}Reset experiment

Permitted assignments

a → 1 a → 2 a → 3 b → 1 b → 2 b → 3 c → 1 c → 2 c → 3

Maximum matching size: 3. a → 1; b → 2; c → 3 All three people can receive distinct tasks.

For S={a, b, c}, its neighbor set N(S)={1, 2, 3}. Thus |S|=3, |N(S)|=3, and deficiency |S|−|N(S)|=0. This subset passes Hall’s inequality; the other subsets still need checking.

All eight left subsets were checked. Every subset satisfies Hall’s inequality. A minimum vertex cover is left {a, b, c} together with right {}, containing 3 vertices. Every edge touches this cover.

Any matching has at most as many edges as any vertex cover: distinct matched edges require distinct covering vertices. The displayed matching and cover have equal size, certifying optimality independently of the search. Hall’s condition characterizes full left matchings in finite bipartite graphs; the general theorem requires a proof, not this three-by-three enumeration.

Remove one edge from a full matching, then decide whether another matching repairs it. Try the one-shared-task graph and explain its deficient subset. This bounded explorer enumerates matchings and covers; it is not an efficient algorithm for large graphs. Positions do not encode distance. Settings are temporary.

Use the live exploration to add or remove eligibility edges, inspect a maximum matching and test all left subsets. Settings are temporary. The fixed example below is separate from the live controls.

Task	Eligible workers
A	1, 2
B	2
C	2, 3

A→1, B→2, C→3 is a full matching. Remove edge C→3 and inspect S consisting of all three tasks: its neighbor set has size two, providing a Hall obstruction.

Understand

A matching is a set of edges with no shared endpoints. If it covers every vertex in left part L, then for each S⊆L its matched partners are distinct members of N(S), proving size (N(S))≥size (S). For sufficiency, choose a maximum matching M and suppose a left vertex u is unmatched. Explore alternating paths from u: move left to right on edges outside M, and right to left on edges in M. A reachable unmatched right vertex would give an augmenting path; flipping its edge statuses increases the matching by one, impossible. Thus every reachable right vertex is matched.

Apply

Let S and T be the reachable left and right sets. Every neighbor of a vertex of S lies in T: an unmatched edge can be traversed, while a matched edge from a nonroot reachable left vertex leads back to its already reached partner. Conversely every right vertex reached is a neighbor of S, so T=N(S). The matched partners give a bijection from T to S excluding the unmatched root u. Therefore size (N(S))=size (S)−1, contradicting Hall’s condition. This proves sufficiency and simultaneously describes how a failed maximum matching produces a deficient subset.

Continue

For several unmatched left roots explored together, the same construction yields a deficiency at least their number; the single-root proof is enough for the theorem. A family of sets has distinct representatives exactly when its membership graph has a matching covering the set-index side. The theorem assumes finite sets here. The widget enumerates a bounded small case, while the proof covers all finite bipartite graphs. A verified matching is a feasibility certificate; a matching and equal-size vertex cover, developed next, certify maximum size even when a full assignment is impossible.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with pair an optimal matching with a vertex cover.