Questions: Bipartite Graphs: Detection and Two-Coloring

Question 1

You run BFS-based 2-coloring on a graph and find that two adjacent vertices both receive color 'red.' What can you conclude?

• A. The graph has a triangle (3-cycle), which disqualifies bipartiteness
• B. The graph contains an odd-length cycle, so it is not bipartite
• C. The graph contains an even-length cycle, so it is not bipartite
• D. BFS was applied incorrectly; restarting from a different vertex may succeed

Answer: (B)

A same-color conflict during 2-coloring means the graph is not bipartite. The conflict corresponds to an odd-length cycle — specifically, the BFS tree path between those two vertices combined with the edge between them forms an odd cycle. The cycle need not be a triangle; cycles of length 5, 7, etc. also cause conflicts. A graph can lack triangles entirely and still be non-bipartite if it has a longer odd cycle (e.g., a 5-cycle).

Question 2

A graph has n vertices and n−1 edges and is connected. Is it necessarily bipartite?

• A. Yes — any tree is bipartite because trees have no cycles at all
• B. Yes — any graph with fewer than n edges is bipartite
• C. No — a connected graph with n−1 edges might still contain odd cycles
• D. No — bipartiteness only applies to dense graphs

Answer: (A)

A connected graph with n vertices and n−1 edges is a tree, and all trees are bipartite. Trees contain no cycles at all, so they trivially satisfy the condition of having no odd cycles. The 2-coloring of a tree is straightforward: BFS assigns alternating colors down each branch and never encounters a conflict. This is a useful special case: whenever you know a graph is a tree (or forest), you also know it is bipartite.

Question 3

A graph with no triangles (3-cycles) is very likely to be bipartite.

• T. True
• F. False

Answer: False

This is a classic misconception. Bipartiteness requires the absence of ALL odd-length cycles, not just triangles. A 5-cycle (pentagon) is not bipartite — it contains no triangle, yet it has an odd cycle. Try 2-coloring a 5-cycle: alternating red/blue around the ring, you return to the start needing the wrong color. The correct characterization is: a graph is bipartite if and only if it contains no odd-length cycle of any length.

Question 4

Bipartite graph detection using BFS runs in O(V²) time because it should check most pairs of vertices.

• T. True
• F. False

Answer: False

BFS-based 2-coloring runs in O(V + E) — the same time complexity as BFS itself. Each vertex is visited once and colored once; each edge is examined once to check whether its endpoints have conflicting colors. There is no need to check all vertex pairs. This linear time complexity is one of the important practical points about bipartite detection: it is cheap to test and enables efficient algorithms like bipartite matching (Hopcroft-Karp) to begin with a linear-time feasibility check.

Question 5

Explain why an odd-length cycle prevents a graph from being 2-colorable, and why an even-length cycle does not.

Model answer: In a 2-coloring, adjacent vertices must receive opposite colors. Walking around a cycle and alternating colors, each step flips the color. After k steps, you return to the start; if k is even, you have flipped an even number of times and end with the starting color — no conflict. If k is odd, you end with the opposite color, creating a conflict with the starting vertex. Even cycles can always be 2-colored; odd cycles cannot.

This parity argument is the heart of the bipartite theorem. It shows that the obstruction to bipartiteness is exactly odd cycles — not self-loops, not even cycles, not any other structure. The BFS 2-coloring algorithm directly implements this check: a same-color conflict between an edge's endpoints means there is an odd-length path in the BFS tree connecting them, and that path plus the edge form an odd cycle.