You run a BFS coloring algorithm on a graph: start at vertex A, color it red, and alternate colors as you traverse edges. At some point you find an edge connecting two vertices that would both need to be colored red. What does this tell you about the graph?
AThe graph is bipartite with an unusual structure requiring more than 2 colors
BThe graph contains an odd-length cycle and is therefore not bipartite
CThe graph contains an even-length cycle which prevents proper 2-coloring
DThe BFS coloring algorithm failed — restart from a different vertex
When alternating colors in BFS fails — both endpoints of an edge need the same color — you have discovered an odd-length cycle. Traversing an odd cycle with alternating colors always forces you back to the starting vertex needing the opposite color from what it already has, creating the contradiction. This is not a failure of the algorithm: it is exactly how the algorithm detects non-bipartiteness. Even-length cycles cause no such contradiction, which is why they are compatible with bipartiteness.
Question 2 Multiple Choice
A graph has vertices {1, 2, 3, 4} and edges {1-2, 2-3, 3-4, 4-1}, forming a 4-cycle. Is this graph bipartite?
ANo — any cycle graph is non-bipartite
BYes — color {1, 3} red and {2, 4} blue; no two adjacent vertices share a color
CNo — the graph has an even number of vertices but an odd number of edges
DYes — but only because the graph has exactly four vertices
C4 (the 4-cycle) is bipartite: partition the vertices into {1, 3} and {2, 4}. Every edge runs between the partitions, never within one. Alternatively: C4 contains only even-length cycles (the single cycle has length 4), so by the odd-cycle theorem it is bipartite. The common misconception is that all cycles are non-bipartite — only odd cycles are. Even cycles can always be 2-colored by alternating red and blue around them.
Question 3 True / False
A graph is bipartite if and only if it contains no odd-length cycles.
TTrue
FFalse
Answer: True
This is the fundamental characterization theorem for bipartite graphs. The 'if' direction: if there are no odd cycles, the BFS coloring algorithm always succeeds — alternating colors around even cycles creates no contradiction. The 'only if' direction: if the graph is bipartite (2-colorable), then any cycle must alternate colors around it; an odd cycle would force the start vertex to need both colors simultaneously, which is impossible in a valid 2-coloring. So odd cycles are precisely the obstruction.
Question 4 True / False
A complete graph on 4 vertices (K4) is bipartite because its vertex set can be split into two groups of 2.
TTrue
FFalse
Answer: False
K4 is not bipartite. Although it has 4 vertices that can be split into two groups of 2, every vertex is connected to every other vertex — including vertices within the same group. More decisively: K4 contains triangles (3-cycles), which are odd-length cycles. By the odd-cycle theorem, any graph containing an odd cycle cannot be bipartite. Bipartiteness requires that no edges exist within each partition, which K4 violates for any partition.
Question 5 Short Answer
Why do odd-length cycles prevent a graph from being 2-colored, while even-length cycles do not?
Think about your answer, then reveal below.
Model answer: When you traverse a cycle and alternate colors, you need the first and last vertex to receive different colors (since they are the same vertex). An even cycle has an even number of steps, so alternation returns you to the starting color — no contradiction. An odd cycle has an odd number of steps, so alternation returns you to the opposite color, creating a conflict: the vertex would need to be both red and blue simultaneously.
The parity of cycle length is the key. Think of 2-coloring as a checkerboard pattern forced by the edges: each step flips the color. After an even number of steps, you are back to the original color. After an odd number of steps, you are at the flipped color. A cycle forces the first and last vertex to be the same node, so even steps work (same color required, same color produced) and odd steps fail (different color produced from what is required).