Bipartite Graph Interview Questions: Disconnected Components and Odd-Cycle Evidence

Bipartite graph interview questions usually begin with “can this graph be split into two groups?” The harder part comes next: handling every disconnected component, explaining why a color conflict proves an odd cycle, and returning that cycle as evidence instead of a bare false. A strong answer treats two-coloring as a certificate problem. If the graph is bipartite, return a color for every vertex. If it is not, return an odd cycle that a reviewer can inspect.

This guide extends that exercise with component coverage, self-loops, parallel edges, cycle reconstruction, iterative traversal, and parity union-find. Those question records describe individual practice prompts; they do not prove that every employer uses the same format.

Bipartite Graph Interview Questions: Quick Answer

Maintain color[v] as -1 for unseen, 0 for one side, and 1 for the other. Loop over every vertex. When an unseen vertex starts a new component, assign color 0 and run BFS or iterative DFS. For each undirected edge (u, v), color an unseen neighbor with color[u] ^ 1; if an already-colored neighbor has color[v] == color[u], the graph is not bipartite.

That scan is O(V + E) with an adjacency list. Starting only from vertex 0 is incomplete because a different component may contain the odd cycle. A self-loop conflicts immediately. Parallel edges do not change the answer. BFS is convenient when the follow-up asks for evidence because parent and depth arrays let you turn a same-color conflict edge into an explicit odd cycle.

Define the contract before choosing the traversal

“Check whether the graph is bipartite” leaves several decisions open. Ask what the input contains and what failure output must prove.

Contract question	Why it changes the implementation	Sensible default
Can the graph be disconnected?	One traversal may miss a bad component	Scan all vertices
Are isolated vertices included in n?	They still need a valid color	Give each unseen isolate either color
Can self-loops or duplicate edges appear?	A self-loop fails; duplicates are harmless	Validate naturally during edge scan
Return boolean, coloring, or odd cycle?	Evidence needs parent and depth state	Preserve enough state to reconstruct
How large can a path be?	Recursive DFS may overflow the call stack	Use BFS or an explicit stack

The bipartition is not unique. Every connected component can flip all of its colors without changing validity. If exact output is graded, define a deterministic rule such as visiting start vertices in numeric order and adjacency lists in input order.

The invariant is an edge constraint

For every processed edge (u, v), the required equation is

color[u] XOR color[v] = 1

When v is unseen, assigning color[v] = color[u] ^ 1 satisfies the equation. When v already has a color, the traversal checks the equation instead of recoloring it. Recoloring on conflict hides the contradiction and can loop forever.

BFS levels explain the same invariant geometrically. Vertices at even distance from a component root receive one color; vertices at odd distance receive the other. Every tree edge crosses between consecutive levels. If an edge connects two vertices of the same color, their root paths have the same parity. Combining those paths with the conflict edge yields an odd closed walk, from which an odd cycle can be extracted.

This is a graph-theory fact. UIUC's CS 473 notes state the characterization that an undirected graph is bipartite exactly when it has no odd-length cycle, and also describe a linear-time algorithm that can output an odd cycle.

Scan every disconnected component

from collections import deque

def two_color(adj: list[list[int]]) -> tuple[bool, list[int]]:
    n = len(adj)
    color = [-1] * n

    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        q = deque([start])

        while q:
            u = q.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return False, []

    return True, color

The outer loop is part of the algorithm, not cleanup. Consider component {0,1} with edge 0-1 and a separate triangle 2-3-4-2. BFS from 0 succeeds, but the graph is not bipartite. The next unseen start eventually reaches the triangle and finds the conflict.

An isolated vertex starts a one-node component and uses only one color. That is valid: the requirement constrains edge endpoints, and the component has no edges. An empty graph is also bipartite under the usual definition.

Return an odd cycle, not just false

Store parent[v] and depth[v] when each vertex is discovered. Suppose an inspected edge (u, v) joins vertices with the same color. Walk the deeper endpoint upward until both depths match, then walk both endpoints upward together until they meet. Their meeting point is the least common ancestor in the BFS tree. The tree path from that ancestor to u, the conflict edge u-v, and the tree path from v back to the ancestor form the witness.

def odd_cycle(u: int, v: int, parent: list[int], depth: list[int]) -> list[int]:
    if u == v:
        return [u, u]  # one-edge self-loop

    left, right = [], []
    a, b = u, v
    while depth[a] > depth[b]:
        left.append(a)
        a = parent[a]
    while depth[b] > depth[a]:
        right.append(b)
        b = parent[b]
    while a != b:
        left.append(a)
        right.append(b)
        a = parent[a]
        b = parent[b]

    left.append(a)                         # common ancestor
    path_u_to_v = left + list(reversed(right))
    return path_u_to_v + [u]              # close with conflict edge v-u

For conflict edge 3-4, with tree paths 0-1-3 and 0-2-4, the function returns [3, 1, 0, 2, 4, 3]. It contains five edges, so it is odd. Every consecutive pair except the last is a tree edge; the last pair is the observed conflict edge.

Returning the actual vertices exposes reconstruction bugs that a boolean test cannot reveal. Verify that the first and last vertex match, the edge count is odd, and every consecutive pair is present in the graph.

Why the conflict witness must be odd

Color equals BFS depth parity. A conflict edge joins equal colors, so depth[u] and depth[v] have the same parity. Let the common ancestor have depth d. The two tree-path lengths are depth[u] - d and depth[v] - d. Their sum is even because the depths have the same parity. Adding the one conflict edge makes the cycle length odd.

The reconstruction removes the shared prefix of the two root paths. Without that least-common-ancestor step, concatenating whole root paths can repeat vertices and return an odd closed walk rather than a simple cycle. The closed walk still proves non-bipartiteness, but an interviewer asking for a cycle normally expects the cleaner witness.

The converse is also direct. Along any cycle, two colors must alternate. After an odd number of edges, the final edge demands that the starting vertex have the opposite color from itself, which is impossible. Thus an odd cycle prevents a valid bipartition.

Handle self-loops, parallel edges, and malformed adjacency

Input feature	Correct result	Reason
Self-loop (u, u)	Not bipartite	One vertex cannot differ from itself
Two parallel copies of (u, v)	Same result as one edge	Both impose the same parity constraint
Isolated vertex	Bipartite component	No edge constraint is violated
Even cycle	Bipartite	Alternating colors return consistently
Odd cycle	Not bipartite	Alternation collides on the closing edge

If the input is an undirected edge list, add both directions. If the input is an adjacency list, clarify whether symmetry is guaranteed. Silently accepting a half-directed representation changes the problem. Validate out-of-range endpoints when input can be malformed; do not let a language-specific index error masquerade as graph logic.

For V vertices and E undirected edges, building the adjacency list costs O(V + E) space and time. The traversal examines each stored direction once, so it is also O(V + E). The queue, colors, parents, and depths use O(V) additional space.

BFS, DFS, and parity union-find answer different follow-ups

BFS and iterative DFS both produce a valid two-coloring in linear time. BFS naturally supplies levels and readable parent paths. Iterative DFS may use less frontier memory on some graphs, but its tree is not a shortest-path tree. Recursive DFS is concise but unsafe when the input can be a chain of hundreds of thousands of vertices.

Parity union-find is useful when edges arrive online. Store for each node the XOR parity from the node to its disjoint-set parent. An edge (u, v) requires opposite parity. If the endpoints are already in the same set, compare their implied parity; equality reveals a contradiction. If they are in different sets, merge the roots while setting the new parent parity to preserve the constraint.

Union-find can answer whether all constraints seen so far remain consistent. It does not naturally return the explicit odd cycle because path compression discards the original graph path. If evidence is required, keep a separate spanning forest or use traversal after detecting the contradictory component. Choose the data structure from the output contract, not from novelty.

Diagnose common failures with small counterexamples

Symptom	Minimal test	Likely error
Returns true for a hidden triangle	edge plus separate triangle	Traversed only from vertex 0
Loops or changes old colors	triangle	Recolored instead of reporting conflict
Crashes on a long chain	200,000-node path	Recursive DFS exhausted the stack
Rejects duplicate edges	two copies of 0-1	Counted edges instead of checking constraints
Returns a non-cycle witness	conflict below a shared ancestor	Did not remove the common path prefix

Use the smallest failing graph and name which invariant broke: component coverage, unseen-node assignment, checked-edge parity, or witness reconstruction. That explanation is more persuasive than presenting a memorized isBipartite loop.

Final takeaway

A complete bipartite-graph answer does four things. It colors from every unseen vertex, checks every edge against an opposite-color invariant, treats a conflict as structural evidence, and matches the data structure to the required output. A boolean needs only colors. A useful diagnostic needs parents and depths. An online stream may justify parity union-find.

Practice the standard check, then add one requirement at a time: disconnected components, a self-loop, deterministic colors, an explicit odd cycle, and incremental edges. Continue with the five linked Coding & Algorithms questions, and for every rejection be ready to show the exact edge or cycle that makes the constraints impossible.

Sources and Further Reading

• Princeton Algorithms: BipartiteX API
• UIUC CS 473: Bipartite Graph Characterization
• Stanford CS103: Graph Theory Problem Set

University and library references support the graph-theory claims.*