Bipartite Graphs and Odd Cycles
A graph is bipartite if splits into two parts and with every edge joining to — no edge lies inside or inside . Theorem: is bipartite if and only if it has no cycle of odd length.
The two parts are exactly a proper -coloring: color every vertex of white and every vertex of black, and no edge ever joins two same-colored vertices. A cycle has to alternate colors as it goes around, so after an even number of steps it returns to its starting color — but after an odd number of steps it would need the start and end vertex (the very same vertex) to hold opposite colors at once, which is impossible. That gives the easy half of the theorem outright. The hard half — that having no odd cycle ANYWHERE in the graph is also enough to guarantee a full -coloring — is proved in Why It Works by growing the coloring outward from one vertex at a time, exactly as a breadth-first search would.
Let have one vertex for each of the binary strings of length , with an edge between two strings whenever they differ in exactly one bit — , , and so on. Color each vertex by the parity of its number of s: (even) and (odd). Flipping one bit always changes the number of s by exactly , so it always changes parity — every one of the edges joins to , and is bipartite.
Let have a hub joined to every vertex of a -cycle — rim edges plus spokes, edges on vertices. The hub and any two consecutive rim vertices form a triangle, for instance : the edges , , are all present, a -cycle. An odd cycle, so by the theorem is not bipartite — no -coloring can work, however the colors are assigned.
Start from the complete bipartite graph on , (all cross edges), bipartite by construction. Add a single edge inside . Is the result still bipartite? Now form a triangle: is the new edge, and , are both original cross edges — a -cycle has appeared. By the theorem the graph is no longer bipartite: one edge inside a part is already enough to destroy it, no matter how many legitimate cross edges surround it.
Triangle-free is not the same as bipartite. The -cycle has no triangle at all — no three mutually adjacent vertices — yet it is still not bipartite, since it is itself an odd cycle of length . The theorem rules out EVERY odd length, not just length ; checking only for triangles catches none of the longer odd cycles.
Five chemicals are arranged so each is incompatible only with its two neighbors in a cycle: . Can they be sorted into two storage rooms so no two incompatible chemicals share a room?
Show the answerHide the answer
This asks whether the incompatibility graph — the -cycle — is bipartite. It is an odd cycle (length ), so by the theorem it has no proper -coloring: however the five are split into two rooms, one room holds at least of the , and among any chemicals from a -cycle two are consecutive, hence incompatible. **No** — two rooms are not enough; splitting them , , into three rooms does work.
Matchings
A matching is a set of edges no two of which share a vertex. saturates a vertex if some edge of touches it. is maximal if no edge can be added to it without breaking the no-shared-vertex rule; is maximum if no matching of the graph is larger; a perfect matching saturates every vertex. The matching number is the size of a maximum matching, and it can never exceed in a bipartite graph, since each -edge uses one vertex from each side.
Maximal only means "stuck for now" — no single edge happens to extend it — while maximum means "as large as any matching could possibly be." Every maximum matching is maximal (if it could be extended it would not be largest), but the next example shows the reverse fails badly: a careless, greedy choice of edges can get stuck far short of maximum. Recognizing when a matching truly cannot be beaten is the deeper question, answered by Berge's theorem in Why It Works: a matching is maximum exactly when it admits no augmenting path, an alternating path of unmatched/matched/unmatched/… edges that starts and ends at unsaturated vertices. Hall's theorem and Konig's theorem, next, both grow out of this same alternating-path idea.
On the path (edges ), the single edge is a matching: it is maximal, since both and touch an already-saturated vertex ( or ) and cannot be added. Yet it leaves and unsaturated, and is itself an alternating path from one unsaturated vertex to the other — unmatched , matched , unmatched . Flipping every edge on it (drop , add and ) gives , a matching of size that saturates all vertices: a perfect matching, and since for its natural bipartition , it is maximum.
Three students each like exactly two of three project slots , forming the -cycle of preferences . Can every student get a slot they like, each slot going to one student? Try : all three edges are in the preference list, and are six different vertices, each appearing exactly once across — a perfect matching. Every student is satisfied.
A hub is compatible with three candidates (edges ) and the candidates are compatible with nothing else. Any matching can use at most one of these edges, since all three share the vertex : , even though there are candidates — matched to the single vertex , at most of them ever gets saturated at a time, no matter which edge is chosen.
Believing a matching is maximum just because no edge can be added to it right now. The matching on the path is exactly this trap: it is maximal (stuck), yet is twice as large. "Stuck" only rules out adding ONE edge at a time; an augmenting path can grow a matching by removing one edge and adding two, which a purely greedy check never considers.
A bipartite graph has and . A matching saturates all of . Must it be maximum, even though it leaves vertices of unsaturated?
Show the answerHide the answer
Every matching uses one vertex from each side per edge, so its size can never exceed . A matching that saturates all of already has size , the largest any matching could possibly reach — **yes, it must be maximum**, even though it is far from perfect on the side.
Hall's Marriage Theorem
For a bipartite graph with parts , write for the set of all neighbors (in ) of a subset . Hall's Marriage Theorem: a matching saturating every vertex of exists if and only if for EVERY subset — Hall's condition.
Necessity is immediate: the vertices of must be matched to distinct vertices, all of which are neighbors of by definition, so had better contain at least that many. The theorem's force is that this one family of simple counting checks, one inequality per subset, is also SUFFICIENT — no other obstruction can ever block an -saturating matching. The name comes from the classical story: is a set of people, a set of acceptable marriage partners, and an edge means "willing to marry." Why It Works proves sufficiency by induction, peeling off one matched pair at a time.
Applicants apply to jobs with qualified for , for , for . Every subset of must be checked: the three singletons each have ; the three pairs have , , , all of size ; and , size . Hall's condition holds throughout, so an -saturating matching exists — for instance .
Applicants apply to jobs , but and are BOTH qualified only for job , while is qualified for all of . The full set has size , which looks fine — but the pair has , size : Hall's condition fails on this smaller subset. No matter how jobs are assigned, and both need job and only one can have it, so no -saturating matching exists; the best possible matching has size (for instance ), leaving one of unmatched.
Take on , and delete the perfect matching , leaving every vertex with degree exactly — a -regular bipartite graph. For any , counting edges leaving gives exactly , and every one of those edges lands in , where each vertex can absorb at most of them (its own degree); so , i.e. — Hall's condition holds automatically, for any -regular bipartite graph, not just this one. A perfect matching must exist, and indeed is one: four edges of the remaining ones, touching all vertices exactly once.
Checking Hall's condition only on itself, rather than on every subset. In the job example above, has size — the full-set check passes — yet the SMALLER subset is where the condition actually fails. Hall's theorem demands the inequality for every one of the subsets; the full set alone proves nothing.
People are qualified for slots as follows: and for only, for , for . Does an -saturating matching exist?
Show the answerHide the answer
Check the subset : its neighborhood is , of size , while . Since , Hall's condition fails on this subset. **No** — three people () compete for only two slots () between them, so no matching can saturate all of , regardless of 's independent access to .
Konig's Theorem and Vertex Covers
A vertex cover is a set touching every edge (each edge has at least one endpoint in ). Its minimum size is . For ANY graph, : the edges of a maximum matching are pairwise disjoint, so covering all of them needs at least one cover vertex per edge, and no two matching edges can share that vertex. Konig's theorem: for a BIPARTITE graph, equality always holds, .
The inequality costs nothing and holds everywhere, matching or no matching, bipartite or not; it is Konig's theorem that is special, promising a cover no larger than the matching that lower-bounds it. The classical construction (Why It Works) starts from a maximum matching , marks every vertex reachable from an unsaturated -vertex by an alternating path, and builds the cover from the unmarked part of together with the marked part of — turning Hall's theorem's subset into an explicit, provably minimum set of vertices. This equality is also the bipartite case of the much more general max-flow min-cut theorem, previewed in Directed Graphs and Flows.
Recall the bottleneck graph from Hall's Marriage Theorem: applying to jobs , with . Its maximum matching has size , for instance . A cover of size is : edge and both touch , while all touch — every edge is covered. Since always and this cover achieves , Konig's theorem is confirmed: , by a cover that mixes one vertex from each side.
A hub connects to leaves and nothing else connects them (recall A matching can never beat the smaller side, Matchings). The single vertex touches all three edges , so ; and always, so exactly. The minimum cover need not involve the three leaves at all — one well-chosen vertex can cover arbitrarily many edges if they all meet there.
In the graph above ( vertices, ), find a maximum independent set — a set of vertices with no edge between any two of them. By Gallai's identity, a maximum independent set has size in any graph. Try : and are not adjacent (both only touch ), and are not adjacent (both lie in , and has no internal edges), and none of is adjacent to or (their only neighbor is ). All pairs are checked and none is an edge: is independent, of size , matching the formula exactly.
Assuming outside bipartite graphs. The triangle has (any two of its three edges share a vertex, so only one can be matched) but (one vertex always misses the opposite edge; two vertices, say and , are needed to touch all three edges ). Konig's theorem needs the bipartite hypothesis; dropping it can make strictly larger than .
Find and for the path (seven vertices, six edges), and exhibit both a maximum matching and a minimum cover.
Show the answerHide the answer
A maximum matching takes every other edge: , size , leaving only unsaturated (no larger matching fits in edges on a path). A cover of size is : edge and touch , and touch , and touch — all six edges covered. Since always and this cover attains , Konig's theorem gives .
Stable Matchings
Given two equal-size sets, say men and women, each person ranks every member of the other set. A perfect matching has a blocking pair if some unmatched man and woman BOTH prefer each other to their current partners. A matching with no blocking pair is stable. Gale-Shapley theorem: a stable matching always exists, and the deferred-acceptance algorithm (men propose in order of their own preference; a woman holds her best offer so far and rejects the rest) always finds one.
This is a different kind of question from Hall's and Konig's theorems: those assumed a fixed yes/no compatibility graph and asked whether a perfect matching exists at all; here the underlying graph is already complete (everyone ranks everyone), so a perfect matching trivially exists, and the question is which ONE to pick given everyone's preferences. A blocking pair is a standing threat to break the matching apart, since both people involved would rather be with each other, so stability is the only kind of matching that can actually survive once people are free to renegotiate. Why It Works proves the algorithm always terminates and never leaves a blocking pair behind.
Men rank women as ; ; . Women rank men as ; ; . Round : , , ; holds over (her list ranks above ), rejecting . Round : (his next choice); already holds , and her list ranks above , so rejects again. Round : , his last choice, accepted. The result is . Checking every one of the possible pairs confirms no blocking pair: each person who is not with their top choice (only , matched to his last choice ) is paired with someone who in turn prefers their own current partner, so neither side wants to break away.
Men and women all rank above (for the men) and above (for the women): ; . Is the matching stable? Check the pair , who are not matched to each other: prefers to his current partner (since ranks first), and prefers to her current partner (since ranks first). Both prefer each other to their current partners, so is a blocking pair: this matching is unstable, and it would unravel as soon as and compared notes. The stable matching here is the "obvious" one, , where every blocking attempt fails because each person already has their first choice.
Run the SAME preferences as the first example, but let the women propose. Round : , , ; holds over (his list ranks above ), rejecting . Round : (her next choice); already holds , and his list ranks above , so rejects again. Round : , accepted. The result is — DIFFERENT from the men-proposing matching found before, yet checking all pairs again shows it too has no blocking pair. The same preferences admit (at least) two different stable matchings, and each man does WORSE here than under his own side's proposals ( gets instead of ; gets instead of ) — the content of the proposer-optimality theorem in Why It Works.
Thinking a matching is unstable just because ONE person is unhappy. In the first example, is matched to his last choice and would clearly rather have or — but that alone changes nothing, since instability needs a MUTUAL preference. prefers to , yet (matched to , her top choice) does not prefer back; prefers to , yet (matched to , her second choice but still above ) does not prefer either. One-sided wishful thinking never breaks stability; both members of a pair must prefer each other.
Men rank and ; women rank and . Is the matching stable?
Show the answerHide the answer
Check the only other possible pair, and (and symmetrically ): 's own ranking is , so already prefers her CURRENT partner over — she has no interest in switching, so cannot be a blocking pair no matter what prefers. The same reasoning kills , since ranks her current partner above . Every woman already holds her own top choice, which alone guarantees no blocking pair can form. **Yes** — the matching is stable.
Why It Works
Necessity was shown in Hall's Marriage Theorem: if saturates , the vertices of are matched to distinct vertices of . For sufficiency, induct on . If , Hall's condition on the single vertex gives , so has some neighbor to match to. Assume the theorem for all smaller vertex sets, and suppose Hall's condition holds for with . Case 1: every nonempty proper subset satisfies the STRICT inequality . Pick any and any neighbor of (one exists since ), and match to . In the graph with and deleted, any has , so , using the strict inequality from Case 1 (as is a proper subset of ). So satisfies Hall's condition on ( vertices); by induction it has an -saturating matching, and adding saturates all of . Case 2: some nonempty proper subset has exactly (equality, the tightest possible). Let . Any subset of has the same neighbors in as in the induced bipartite graph on (its neighbors already lie in by definition of ), so Hall's condition holds there too; since , induction gives a matching that perfectly matches to . Now let be with and deleted, on parts and . For any : (every neighbor of outside is a neighbor in , and every neighbor of is already in ), and these two pieces are disjoint, so (using Hall's condition in on , and ). So satisfies Hall's condition on , which is smaller than since ; by induction it has an -saturating matching . Since and use disjoint vertex sets, saturates all of . Either case produces an -saturating matching, completing the induction.
The inequality holds for every graph (Konig's Theorem and Vertex Covers): a maximum matching's edges are disjoint, so a cover needs a distinct vertex for each. For the reverse inequality in a bipartite graph, fix a maximum matching . Let be the vertices leaves unsaturated, and let be every vertex reachable from by an -alternating path — starting with a non-matching edge, then alternating matching/non-matching. Write , . Lemma: every is -saturated. If some reachable were unsaturated, the alternating path reaching it (starting at an unsaturated , ending at the unsaturated , alternating the whole way) would be an augmenting path: flipping every edge on it — dropping its matching edges, adding its non-matching edges — produces a matching one edge larger than (each endpoint along the path keeps exactly one incident edge in the new matching, and the two endpoints gain an edge instead of having none), contradicting that is maximum. So every has a partner , and that partner is itself reachable (the path to extends by its matching edge to ), so . Let . is a vertex cover: take any edge with and (the only way could avoid ), and derive a contradiction. If : since consists of unsaturated vertices, (it has the matching edge ), so was reached via its OWN matching edge from some already-reachable with ; but is unique, so , putting — contradiction. If : the alternating path reaching (either the trivial path if , or one ending with a matching edge into ) extends by the non-matching edge without breaking the alternation, reaching — so , again a contradiction. So no such edge exists, and covers every edge. , so : every is saturated (unsaturated vertices all lie in ), and its partner cannot lie in (if it did, the matching edge would make reachable too, contradicting ) — so these vertices match, via , into DISTINCT vertices of . Separately, by the Lemma every matches via into . These two families of matching edges are disjoint (one ends in , the other in ), giving distinct edges of , so . Combined with , this forces , so all are equal: .
Termination and perfection: each round, some man proposes to a woman he has never proposed to before, and each of the men has only women on his list, so the algorithm halts within rounds. Once engaged, a woman is NEVER free again — she only ever replaces her partner with someone she prefers more, never drops to nobody. Suppose the algorithm ended with some man unmatched; since he was never (re-)accepted, he must have proposed to and been rejected by every one of the women. Each such rejection happened because that woman was already engaged to someone else at the time, and since engaged women stay engaged, all women are engaged at the end. But a set of engaged women, each holding exactly one man, accounts for distinct engaged men — leaving no room for an -th man, let alone an unmatched among only men total. Contradiction; every man ends matched, and since women only end matched to a proposer, the result is a perfect matching. Stability: suppose the final matching has a blocking pair : prefers to his partner , and prefers to her partner . Since proposes in strictly decreasing order of preference and ended up with , worse than , he must have proposed to at some earlier round and been turned away — either rejected immediately, or accepted then later displaced. At that moment was holding (or came to hold) some man she preferred to . From then on 's held partner only improves (by the no-free-fall rule above), so her FINAL partner is preferred by at least as much as whoever beat that round, which was itself preferred to — so prefers to . This contradicts the blocking pair's assumption that prefers to . So no blocking pair can survive: the matching is stable.
Say a man is better off in a stable matching than in the algorithm's result if he prefers to . Suppose, for contradiction, some man is better off in some stable ; then at some point during the algorithm he must have proposed to and been rejected (he proposes in decreasing order and ends up with something worse than , so was reached and turned down along the way). Among every such rejection, across every man and every stable , take the FIRST one to occur in time: woman rejects (immediately, or by later displacing him) in favor of some she currently prefers over . Because this is the FIRST time any woman has rejected her own -partner, the man has not yet (as of this moment) been rejected by — so every woman has proposed to so far, including , ranks at least as high on 's list as does (he proposes in decreasing order, and has not yet been turned away by , so he has not yet reached anyone ranked below her). In particular prefers to , or is indifferent, so prefers at least as much. Now compare this to : prefers to (that is why she just rejected ), and prefers to . That is exactly a blocking pair for — contradicting that is stable. So no such first rejection can exist, and no man is ever better off in any stable matching than in the men-proposing algorithm's result: it is men-optimal.