Bipartite Graphs / 2-Coloring

A graph is bipartite if you can split its nodes into two teams so that every edge runs between the teams and no edge joins two teammates. It comes up whenever a problem asks you to split things into two groups that must stay apart. You test it by trying to color the graph with two colors.

The idea#

Formally, the nodes split into two disjoint sets $V_1$ and $V_2$ that together cover every node, and every edge has one end in each set. An equivalent test is easier to reason about: a graph is bipartite if and only if it has no odd-length cycle. A triangle is the smallest example of failure: color A red, B blue, and C must be both.

Hunting for odd cycles directly is awkward, so in practice you 2-color the graph and watch for a clash:

Pick an uncolored node and give it color 1.
Give every neighbor the opposite color, -1, and keep spreading with BFS or DFS.
If you ever reach a neighbor that already has the same color as the current node, the graph is not bipartite.
Repeat from every uncolored node, because the graph may have several components.

How to spot it#

The hint usually comes as "split into two groups" or as a conflict that must be kept apart.

Cue	What to do
"Can the items be split into two groups with no related pair inside a group?"	2-color with BFS or DFS
"Is the graph 2-colorable?" / "independent sets"	Same test
"Separate people who dislike each other"	Make each dislike an edge, then 2-color
A triangle or other odd loop of relations	Not bipartite

Template#

The input is an adjacency list (graph[u] lists the neighbors of u). Color 0 means uncolored; 1 and -1 are the two teams.

color = 0 for every node
for each start node:
    if color[start] != 0: skip       # colored by an earlier component
    color[start] = 1
    push start onto queue
    while queue is not empty:
        node = pop from the front of queue
        for each nei in neighbors of node:
            if color[nei] == color[node]:
                return not bipartite # edge inside one team
            if color[nei] == 0:
                color[nei] = -color[node]   # opposite team
                push nei onto queue
return bipartite

Every node and edge is handled once, so it runs in $O(V + E)$ time and $O(V)$ extra space.

Beyond interviews: matching and assignment#

The two-team view is useful beyond yes-or-no tests. Bipartite graphs also model pairings between two kinds of things: applicants and jobs, tasks and machines, bikes and racks. "Find the maximum number of non-conflicting pairs" is maximum bipartite matching, usually solved with augmenting paths (Hopcroft-Karp) or by turning it into a max-flow problem. König's theorem says that in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover (the smallest set of nodes that touches every edge). These rarely appear in standard interviews.

Pitfalls#

These are the mistakes that most often cost a correct answer.

Coloring only from node 0 and missing other components.
Using 0 as a color as well as "uncolored".
Adding an undirected edge in one direction only.
Expecting 2-coloring to solve problems that allow more colors: those are a different, usually greedy, problem.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first one.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Is Graph Bipartite?

The input is already an adjacency list. Run the template as it stands, and start from every uncolored node, because the graph may be disconnected.

Hint: Possible Bipartition

The "bad relationship" becomes the edge. Turn each dislike pair into an undirected edge, added in both directions, and 2-color the result.

Hint: Flower Planting With No Adjacent

Four colors are allowed, so this is not a 2-coloring test. Color greedily: give each garden a flower type that none of its neighbors uses yet.

Key takeaways#

Bipartite = the nodes split into two teams with every edge between teams.
Bipartite if and only if there is no odd-length cycle.
Test it by 2-coloring with 1 and -1; a same-color edge means failure.
Start a new coloring from every uncolored node.
Model "must be apart" relations as edges.

Core idea#

A graph is bipartite if its nodes split into two teams and every edge runs between the teams. Test it by 2-coloring the graph.

Key points#

A graph is bipartite if and only if it has no odd-length cycle. A triangle is the smallest failure.
Give a start node color 1 and each neighbor the opposite color, -1.
A neighbor with the same color as the current node means not bipartite.
Start a new coloring from every uncolored node. The graph may have several components.
Model "must be apart" relations as edges. Possible Bipartition turns each dislike into an undirected edge.
Time is $O(V + E)$ . Extra space is $O(V)$ .
Maximum bipartite matching (Hopcroft-Karp, max-flow) is beyond most interviews.

Template#

color = 0 for every node             # 0 means uncolored
for each start node with color 0:
    color[start] = 1; push start onto queue
    while queue is not empty:
        node = pop from the front of queue
        for each nei in neighbors of node:
            if color[nei] == color[node]:
                return not bipartite # odd cycle
            if color[nei] == 0:
                color[nei] = -color[node]; push nei
return bipartite

Pitfalls#

Coloring only from node 0 and missing other components.
Using 0 as a color and as "uncolored".
Adding the dislike edge in one direction only.
Using 2-coloring for problems that allow more colors. Those are a different, usually greedy, problem.

Say it in an interview#

"Bipartite means no odd cycle. 2-color with BFS and fail on a same-color edge."
"Restarting from every uncolored node handles disconnected graphs."