Some graphs split cleanly into two camps -- workers and jobs, students and dorm rooms, donors and recipients -- with every edge crossing between the camps and none inside either one. Pairing up members of those two camps, one-to-one, is one of the most useful things a graph can be asked to do, and both ideas -- the split itself, and the pairing built on top of it -- carry straight through to this course's own network-flow chapter later on.
A bipartite graph is one you can split into two teams where every connection crosses between the teams and none stays inside one. There's a one-step test for this: walk any loop in the graph and count its length. If some loop has an odd number of steps, the split is impossible; if every loop is even, the split always works. A matching is a set of connections that never share a person -- think of each chosen edge as a handshake, and nobody gets to shake two hands in the same round. A matching that pairs off every single person on one side is the best that side could possibly hope for.
A graph is bipartite if its vertices split into two parts so that every edge has one end in each part and no edge sits entirely inside either part. Checking this by trial and error is unnecessary: a graph is bipartite exactly when it contains no cycle of odd length, since walking around any cycle must alternate between the two parts, and returning to the start forces an even number of steps.
A matching is a set of edges, no two of which share an endpoint -- equivalently, a set of pairings where nobody is paired twice. A vertex touched by a chosen edge is saturated; one that isn't is left over. A matching that saturates every vertex on one side of a bipartite graph is the graph-theory version of "everyone on that side gets paired," and deciding exactly when that's possible is itself a whole theorem, worth having ready:
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics II — Combinatorics
The cycle C_6 and the cycle C_7: which are bipartite?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
An even cycle alternates the two parts cleanly; the odd cycle C_7 is itself an odd cycle, the forbidden structure.
Bipartiteness of a cycle comes down to one property of its length -- check that property separately for 6 and for 7.
From Discrete Mathematics II — Combinatorics
How many edges does the complete bipartite graph K_{3,4} have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every left vertex meets every right vertex: 3*4 = 12 edges.
Correct answer
Also accepted:
Why
Quick review
Practice from earlier coursework, pulled in for this topic.
From Discrete Mathematics II — Combinatorics
A student claims the edge sets {ab, cd, ef} and {ab, bc} are both matchings. What is the verdict?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
The first set uses six distinct endpoints; the second repeats b, violating the defining condition.
Check each proposed edge set against the no-shared-endpoint rule separately, listing every endpoint used.
From Discrete Mathematics II — Combinatorics
Which condition defines a matching in a graph?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A matching is any set of pairwise non-adjacent edges; covering every vertex is the stronger, special condition of a perfect matching.
Theorem
Hall's Marriage Theorem
also known as: Hall's condition, the marriage theorem
Recalled from Discrete Mathematics II — Combinatorics · Hall's marriage theorem — first taught there.
Let G be a bipartite graph with parts L and R. There is a matching saturating L (using every vertex of L) if and only if |N(S)| \ge |S| \quad \text{for every subset } S \subseteq L, where N(S) is the set of all vertices in R adjacent to at least one vertex of S.
Necessity. Suppose a matching M saturates L, and let S \subseteq L be any subset. Each vertex of S is matched by M to its own vertex of R, and these matched partners are distinct because no two edges of a matching share an endpoint. Every matched partner of a vertex in S is, in particular, a neighbor of that vertex, so all |S| of them lie in N(S). Hence |N(S)| \ge |S|. Equivalently: if some set S has |N(S)| < |S|, the |S| vertices of S would need distinct partners drawn from fewer than |S| available neighbors, which is impossible — the deficiency |S| - |N(S)| counts vertices of S that must go unmatched.
Sufficiency (sketch). Suppose |N(S)| \ge |S| for every S \subseteq L, and let M be a matching of maximum size. If M did not saturate L, pick an unmatched vertex u \in L and consider all vertices reachable from u by alternating paths (paths whose edges alternate between non-matching and matching edges). Let A \subseteq L and B \subseteq R be the reachable vertices on each side. A standard argument shows every vertex of B is matched (otherwise an augmenting path would let us enlarge M, contradicting maximality) and that B = N(A) with each vertex of A \setminus \{u\} matched into B. Counting then gives |N(A)| = |B| = |A| - 1 < |A|, violating Hall's condition. So M saturates L. The full details of the reachability argument are the standard augmenting-path proof of the theorem.
Confirm a 6-cycle is bipartite
Use the 2 colors to split this 6-cycle into two teams -- no edge should connect two same-colored vertices.
Loading interactive…
Check your understanding (counts toward your progress)
This is a workers-and-jobs graph (w_1,w_2,w_3,w_4 against j_1,j_2,j_3,j_4). Build the largest matching this graph actually has.
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
What this task checks
Structure checked automatically. Whether your ideas are convincing isn't graded, so reread with the checklist.
The compiler says
A model answer
Why
A perfect matching exists here: w_1-j_1, w_2-j_3, w_3-j_2, w_4-j_4 pairs every worker with a distinct job, so the maximum matching size is 4 -- no larger matching is possible once every vertex on one side is already saturated.
Correct answer
Also accepted:
Why
Try pairing each worker with a job that no other worker's best option would also want, so you don't box yourself out of a full matching.
Recipe Test whether a graph is bipartite Use when: you're given a graph, drawn or listed by edges, and asked whether it splits into two sides with every edge crossing between them Goal: a definite classification, backed by either a working two-coloring or the odd cycle that blocks one
Quick recipe
-
1
Choose any vertex in the graph and assign it color 1. This is the seed every other color gets built from.
Example
On the 6-cycle a-b-c-d-e-f-a from the widget above, start at a and color it 1.
Why: the two colors will stand for the graph's two sides, so one vertex has to anchor which side is which before anything else can be assigned.
-
2
For each vertex you've just colored, assign the opposite color to every uncolored neighbor across each edge, working outward across the whole graph.
Example
Continuing from a=1: b=2 (neighbor of a), c=1 (neighbor of b), d=2, e=1, f=2. Check the closing edge f-a: f=2 and a=1 differ, so no conflict.
- a neighbor is uncolored — assign it the opposite color and continue
- a neighbor is already colored the same as the vertex you're extending from — stop, this edge is a conflict
⚡ Shortcut
If the graph is literally a single cycle, skip the coloring walk entirely: just count the cycle's edges. An even count always colors cleanly; an odd count is guaranteed to conflict exactly once, at the closing edge, matching the odd-cycle rule directly.
Why: an edge joining two same-colored vertices would put both its endpoints on the same side, exactly what a bipartite split forbids.
-
3
No conflict after every vertex is colored means the two color classes form a genuine bipartition. A conflict means the graph isn't bipartite, and it exposes an odd cycle.
Example
The 6-cycle finishes clean: \{a,c,e\} against \{b,d,f\}. Running the same process on the 5-cycle a-b-c-d-e-a gives a=1,b=2,c=1,d=2,e=1, and the closing edge e-a repeats color 1 on both ends, a conflict confirming what an odd-cycle count already shows.
- coloring finishes with no conflict — bipartite, with the parts read straight off the two colors
- a conflict appears — not bipartite, and the vertices colored so far trace out an odd cycle
Why: the color-conflict test and the odd-cycle test are the same fact seen two ways, since a graph two-colors successfully exactly when it has no odd cycle.
Common mistakes
- Assuming a graph is bipartite just because no odd cycle jumps out visually, instead of finishing the coloring or finding the conflict explicitly.
- Coloring a neighbor arbitrarily instead of strictly the opposite color of the vertex being extended from.
- Checking only part of the graph when it has more than one component; each component needs its own coloring walk.
- Declaring "not bipartite" from one suspicious-looking edge without actually tracing a full color conflict back to it.
Worked example
Testing bipartiteness with the odd-cycle rule
-
1
Is a 5-vertex graph consisting of a single cycle a-b-c-d-e-a bipartite? This is Steps 2 and 3 of the recipe above, using the single-cycle shortcut instead of a full coloring walk.
-
2
Count the cycle's length: it visits 5 distinct vertices before closing back to a, so it has 5 edges.
-
3
Five is odd, and the odd-cycle rule needs only one such cycle to rule bipartiteness out entirely -- no case-by-case coloring attempt is needed once an odd cycle is found.
-
4\boxed{\text{Not bipartite} - \text{it contains an odd (5-edge) cycle}}
Loading interactive…
Worked example
Spotting a non-matching
-
1
Between the edge sets \{ax, ay\} and \{ax, by\}, which one is a matching?
-
2
Check each set for a shared endpoint: ax and ay both touch a, so choosing both would pair a with two different partners at once.
-
3
Check the other set: ax and by touch four distinct vertices, a, x, b, y -- no vertex repeats.
-
4\boxed{\{ax, by\} \text{ is the matching}}
Loading interactive…
Worked example
Applying Hall's condition to see why a pairing fails
-
1
Three workers, \{1,2,3\}, can each only do jobs from the set \{A, B\} -- every one of them is qualified for both A and B, and for nothing else. Can all three workers be matched to distinct jobs?
-
2
Apply Hall's condition to the full set of workers, S=\{1,2,3\}: the set of jobs reachable from S is only \{A,B\}, since no worker in S is qualified for anything outside that set.
-
3
Hall's theorem requires the reachable-job count to be at least as large as the worker count for every subset, and here |\{A,B\}|=2 is already smaller than |S|=3.
-
4\boxed{\text{No} - \text{Hall's condition fails on } S=\{1,2,3\}, \text{ only 2 jobs reachable for 3 workers}}
No clever assignment can get around this: at least one of the three workers is guaranteed to be left unmatched, since only two jobs exist for all three to compete over.
Who uses this
Scheduling and assignment systems
Course-scheduling software, hospital residency placement, and ride-share driver-to-rider assignment all start from the same structure: one side of people or resources, another side of slots, and edges marking which pairings are feasible. Checking the graph is bipartite is what licenses the fast matching algorithms these systems actually run -- and Hall's condition is the exact test a scheduler applies internally to know, in advance, whether a full assignment is even mathematically possible before it tries to search for one.
Check your understanding (counts toward your progress)
This is prerequisite material from a prior course: what does it mean for a graph to be bipartite?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Degree isn't what bipartite refers to at all.
Component count is unrelated to bipartiteness.
Bipartite graphs can have any number of vertices, split across two groups.
Why
Bipartite means a two-part split exists where every edge crosses between the parts and no edge sits inside either one.
A graph contains a cycle of length 4. Does this rule out bipartiteness?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Even cycles are completely compatible with a bipartite split.
Vertex count beyond the cycle itself isn't the deciding factor.
Edge count elsewhere in the graph doesn't override the odd-cycle test.
Why
The bipartiteness test cares about cycle length parity: an even cycle alternates cleanly between two parts, while an odd cycle can't.
Check the actual length of the cycle against the odd/even test for bipartiteness before assuming any cycle at all is disqualifying.
A graph contains a triangle (a 3-cycle) somewhere inside it. Can the graph be bipartite?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
The rest of the graph being fine doesn't rescue this -- a single odd cycle anywhere is disqualifying.
The triangle being only part of a larger graph doesn't change anything -- it's still present.
The triangle alone is already enough information -- no odd cycle can ever be split into two parts.
Why
The odd-cycle test only needs one bad cycle to fail the whole graph -- a triangle is length 3, odd, and immediately rules out any bipartite split.
Ask whether the odd-cycle test needs the whole graph to be one big odd cycle, or just needs one bad cycle anywhere inside it.
A graph is disconnected, with one component containing an odd cycle and another component containing no cycles at all. Is the whole graph bipartite?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Bipartiteness is a property of the whole graph -- one bad component ruins it even if others are fine.
Disconnection by itself guarantees nothing about bipartiteness.
The odd cycle in the first component is enough information by itself.
Why
A graph is bipartite only if every one of its components is -- a single odd cycle anywhere, in any component, rules out the whole graph.
Decide whether bipartiteness has to hold for the whole graph at once, or can be checked one component at a time.
Apply that scope specifically to the component that contains the odd cycle.
Practice: Testing and using bipartiteness (4 problems · doesn’t affect your progress)
A graph has a 4-cycle and nothing else. Is it bipartite?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
An even-length cycle alternates cleanly between two parts, so it's bipartite.
Yes -- 4 is even
Suppose a graph consists only of a 5-cycle -- is it bipartite?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A 5-cycle can't alternate cleanly between two parts and close back on itself, since 5 is odd.
No -- 5 is odd, and a single odd cycle rules bipartiteness out
A complete bipartite graph has 3 vertices on one side and 5 on the other, with every possible crossing edge present. How many edges does it have?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Every one of the 3 vertices connects to every one of the 5: 3\times 5=15.
Correct answer
Also accepted:
Why
Count how many vertices on the other side each single vertex connects to, then scale that count up.
A graph has two separate components: one contains an odd cycle, the other has no cycles at all. Is the whole graph bipartite?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Bipartiteness requires every component to pass the odd-cycle test -- one failure anywhere rules out the whole graph.
Decide whether bipartiteness gets checked for the whole graph at once, or component by component.
Apply that check specifically to the component holding the odd cycle.
No -- a single odd cycle anywhere disqualifies the whole graph
Check your understanding (counts toward your progress)
A matching saturates 10 out of 14 vertices in a graph. How many vertices are left unsaturated?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Subtract the saturated count from the total: 14 - 10 = 4 vertices are touched by no edge in the matching.
Correct answer
Also accepted:
Why
Subtract the saturated count directly from the total vertex count.
A matching saturates every vertex in the graph. What is this called?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
A maximum matching is only guaranteed to be the largest one available -- it doesn't have to saturate everyone unless one happens to.
Bipartite describes the graph's structure, not this property of the matching.
This isn't standard terminology for the concept described.
Why
Saturating every single vertex is exactly the definition of a perfect matching -- it requires an even number of vertices to even be possible.
Distinguish saturating literally every single vertex from simply being the largest matching available in some graph.
Edges \{AB, CD\} and edges \{AB, BC\} are proposed as matchings. Which set actually is one?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
AB and BC both touch vertex B -- a shared endpoint, which disqualifies the set.
Only one of the two sets avoids a shared endpoint.
One of the two sets has no shared endpoints at all -- check \{AB, CD\} again.
Why
AB and CD touch four distinct vertices with nothing shared -- a valid matching. AB and BC both touch B, disqualifying that set.
Three workers can each only do jobs from a set of two jobs, \{X, Y\} -- every worker qualifies for both, none for anything else. What does this guarantee?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Three workers can't all be perfectly matched to only two jobs -- someone is always left out.
The problem is about worker coverage, not which specific job goes unfilled.
This is a completely ordinary (if unfortunate) hiring situation -- nothing about it is contradictory.
Why
With only 2 jobs reachable by all 3 workers, at most 2 of the 3 can be matched -- at least one worker is guaranteed to be left over, regardless of which pairing is attempted.
Compare the number of workers who need placing against the number of jobs actually reachable by all of them.
Ask what has to happen once more workers exist than there are reachable jobs available to place them in.
Practice: Building and reasoning about matchings (4 problems · doesn’t affect your progress)
Edges AB and CD share no vertex. Do they form a matching together?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
No shared endpoint between the two edges is exactly the matching condition.
Yes
Edges AB and AC both touch A. Do they form a matching together?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Sharing any endpoint, including A here, disqualifies a pair of edges from forming a matching.
No -- they share the endpoint A
A matching saturates every vertex in a 16-vertex graph. How many edges does it use?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
A perfect matching pairs vertices two at a time: 16/2=8 edges.
Correct answer
Also accepted:
Why
Think about how many vertices each single matched edge accounts for, then divide the total accordingly.
A graph has 7 vertices. Can it have a perfect matching?
Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.
Why
Pairing up every vertex requires an even total -- 7 vertices can never all be matched, no matter how the edges are arranged.
Think about how many vertices a perfect matching pairs up at one time.
Check whether 7 vertices can be split evenly into pairs with none left over.
No -- a perfect matching needs an even vertex count, and 7 is odd