During 2-coloring to check bipartiteness, you find you must assign the same color to two adjacent vertices. What does this prove?
AThe graph has a cycle of even length, which disqualifies it from being bipartite
BThe graph contains an odd-length cycle and is therefore not bipartite
CThe graph is disconnected, so the 2-coloring algorithm does not apply
DYou chose the wrong starting color — restart with the opposite color assignment
The 2-coloring algorithm alternates colors as it traverses the graph. A conflict — needing to assign the same color to adjacent vertices — means you have traced a path that returns to a previously colored vertex with the wrong parity. That path forms an odd-length cycle. A graph is bipartite if and only if it contains no odd-length cycle, so a conflict proves non-bipartiteness. Restarting with a different color will not help — the odd cycle is a structural property of the graph.
Question 2 Multiple Choice
In a bipartite job-assignment graph, 3 workers (w₁, w₂, w₃) are all connected exclusively to the same 2 jobs. According to Hall's theorem, what can you conclude?
AA perfect matching might still exist if the other workers have enough options
BNo perfect matching exists, because Hall's condition is violated: |N({w₁, w₂, w₃})| = 2 < 3
CA maximum matching can still include all 3 workers if the 2 jobs are assigned carefully
DHall's theorem does not apply here because the graph is not connected
Hall's condition requires that for every subset S of the Left vertices, |N(S)| ≥ |S|. The subset {w₁, w₂, w₃} has only 2 neighbors, so |N(S)| = 2 < 3 = |S|. Hall's theorem says this bottleneck is both necessary and sufficient to determine that no perfect matching exists — you cannot match 3 workers to only 2 distinct jobs with no sharing.
Question 3 True / False
A bipartite graph can contain cycles, as long as every cycle in it has even length.
TTrue
FFalse
Answer: True
Bipartiteness and the absence of cycles are not the same thing. The bipartite condition bans only odd-length cycles — a path that goes from Left to Right and back must take an even number of steps. Even-length cycles are perfectly compatible with the two-partition structure. Bipartite graphs are frequently cycle-rich; thinking them must be trees is a common misconception.
Question 4 True / False
If most vertex on the Left side of a bipartite graph is connected to at least one vertex on the Right side, a perfect matching is very likely to exist.
TTrue
FFalse
Answer: False
Hall's condition requires that for *every subset* S of Left, the neighborhood N(S) is at least as large as S — not just that each individual vertex has a neighbor. Three workers all connected only to the same one job each have at least one neighbor, but no perfect matching is possible. Individual connectivity is necessary but nowhere near sufficient.
Question 5 Short Answer
Explain what Hall's marriage theorem says, and describe the 'bottleneck' it identifies as the sole obstruction to a perfect matching.
Think about your answer, then reveal below.
Model answer: Hall's theorem states that a bipartite graph has a perfect matching (from Left into Right) if and only if for every subset S of Left vertices, the neighborhood N(S) has at least |S| vertices. The bottleneck is a subset S where |N(S)| < |S| — more vertices in S than they collectively see in the Right. If any such bottleneck exists, no perfect matching is possible; if none exists, a perfect matching is guaranteed.
The 'only if' direction is easy: you cannot match |S| vertices to fewer than |S| distinct neighbors. The 'if' direction (no bottleneck → matching exists) is the substantive content, proved constructively using augmenting paths. Hall's theorem is powerful because it converts a global question (does a perfect matching exist?) into a family of local neighborhood checks.