Skip to content
Tutorials Center
My learning

Topics

Lesson 129 of 225 ยท Graphs

Bipartite Graphs and Coloring

Check whether a graph is bipartite with BFS 2-coloring, understand the odd-cycle rule, solve possible bipartition, try bipartite matching and greedy coloring.

Imagine you must split a group of students into two teams so that nobody is on the same team as a person they dislike. Or assign jobs to applicants where each applicant can do only certain jobs. Or decide whether a map can be colored with just two colors. These questions share one structure: the vertices split into two groups, and every edge connects the two groups, never two vertices inside the same group. A graph with that property is called bipartite.

Checking whether a graph is bipartite is a clean application of breadth-first search: try to color the vertices with two colors so that every edge joins different colors. This lesson shows the algorithm, the beautiful "odd cycle" rule behind it, a famous interview problem, a first look at bipartite matching, and the more general (and much harder) question of coloring with k colors.

What bipartite means

TEXT
bipartite (4-cycle)          not bipartite (triangle)

  L1 ---- R1                       A
   |  \  /  |                     / \
   |   \/   |                    B---C
   |   /\   |
  L2 ---- R2                  B and C are joined, A joins both:
                              any 2 colors fail

Left group:  {L1, L2}
Right group: {R1, R2}
Every edge goes between the groups.

A graph is bipartite exactly when you can paint each vertex red or blue so that no edge has the same color on both ends. The two color classes are the two groups.

The odd-cycle rule

Follow a cycle and alternate colors: red, blue, red, blue, and so on. After an even number of steps you are back at the start with the right color. After an odd number of steps, the last vertex and the first vertex, which are neighbors, would have the same color. That is a contradiction.

So:

A graph is bipartite if and only if it contains no cycle of odd length.

Trees have no cycles at all, so every tree is bipartite (color by depth parity). A triangle, a 5-cycle and any graph containing one are not. The rule lets you reason without running code: you only have to hunt for odd cycles.

The algorithm: BFS 2-coloring

  1. Keep a color for each vertex, initially unset.
  2. For every uncolored vertex, give it color 0 and start a BFS.
  3. When visiting vertex v, for each neighbor w: if w is uncolored, give it the opposite color of v and enqueue it. If w already has the same color as v, you have found an odd cycle: the graph is not bipartite.

The outer loop over start vertices is needed for graphs with several components; each component can be colored independently.

Python Is this graph bipartite?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each vertex is colored once and each edge is checked a constant number of times: O(V + E) time, O(V) space. A DFS works equally well; only the order of visiting differs.

A trace on a 5-cycle

Take the cycle 0 - 1 - 2 - 3 - 4 - 0. Start at 0 with color 0. Its neighbors 1 and 4 get color 1. Vertex 1 colors vertex 2 with 0. Vertex 4 colors vertex 3 with 0. Now vertex 2 looks at its neighbor 3 and finds both have color 0. The edge 2 - 3 joins two vertices of the same color, so the answer is "not bipartite". The odd cycle was found exactly where the two BFS "fronts" meet.

Python Cycles of every length

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The output confirms the rule: even rings pass, odd rings fail.

Problem: possible bipartition

You have n people numbered 1..n and a list of pairs who dislike each other. Can everyone be split into two groups so that no disliking pair is in the same group?

Each person is a vertex and each dislike is an edge. The question is exactly "is the graph bipartite?". A brute force would try all 2^n ways to split people, which is hopeless beyond about 25 people. BFS coloring answers in O(n + m).

Python Possible bipartition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

When the answer is yes, the coloring itself is the split. When people have no dislikes at all, the coloring puts everyone in the first group, which is still a valid split.

Bipartite matching: a first look

Bipartite graphs model assignment problems. The left group is applicants, the right group is jobs, and an edge means "this applicant can do this job". A matching is a set of edges where no vertex is used twice, so each applicant gets at most one job and each job at most one applicant. A maximum matching is the biggest such set.

A greedy pass (give each applicant their first free job) can get stuck. If Ana takes the only job that Ben could do, Ben ends up with nothing, although Ana had a second option. The fix is an augmenting path: when applicant u finds that a wanted job already belongs to v, ask recursively whether v can move to a different job. If so, v moves and u takes the freed job. This is Kuhn's algorithm.

Python Maximum bipartite matching (Kuhn's algorithm)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The augmenting-path search starts once per applicant and visits each edge at most once per start, so the total cost is O(V x E). Faster algorithms exist (Hopcroft-Karp runs in O(E sqrt(V))), and matching is a special case of maximum flow, which you will meet later.

Coloring with more than two colors

What if two colors are not enough? Graph coloring asks for the fewest colors so that neighbors differ. That number is the chromatic number. Bipartite graphs are exactly those with chromatic number at most 2. For 3 or more colors, deciding whether a graph can be colored with k colors is an NP-complete problem: no known algorithm is fast for every input. Scheduling exams so that no student has two at the same time, assigning radio frequencies to nearby towers, and allocating CPU registers are all coloring problems.

A simple fast heuristic is greedy coloring: go through the vertices in some order, and give each the smallest color not used by its already-colored neighbors. It never uses more than maxdegree + 1 colors, but the number it uses depends on the order, as the next example shows on a plain path (which is bipartite and needs only 2 colors).

Python Greedy coloring depends on the order

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With the unlucky order, vertices 0 and 3 both take color 0, then vertex 1 must take 1, and vertex 2, squeezed between color 1 and color 0, needs a third color. A common improvement is to process vertices with the highest degree first.

Common mistakes

  • Coloring only one component. Loop over all start vertices; an odd cycle may hide in a different component.
  • Treating a self loop as harmless. An edge v - v joins a vertex to itself, so its endpoints always have the same color. A graph with a self loop is never bipartite; the check color[w] == color[v] catches it.
  • Using visited instead of color. A plain visited set cannot tell you whether a neighbor has the right color.
  • Forgetting that "no edges" is bipartite. An empty graph, a single vertex and any tree are all bipartite.
  • Confusing matching with coloring. Two colors can be decided in linear time; maximum matching needs augmenting paths; coloring with 3+ colors is hard.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which statement describes a bipartite graph?

    Bipartite means a split into two groups where no edge has both ends inside the same group, equivalently a valid 2-coloring.
  2. 2. A graph contains a cycle of length 7. Can it be bipartite?

    Alternating two colors around an odd cycle forces two adjacent vertices to share a color. One odd cycle is enough to make the whole graph non-bipartite.
  3. 3. What is the time complexity of the BFS 2-coloring test on a graph stored as an adjacency list?

    Each vertex is queued once and each edge is inspected a constant number of times.
  4. 4. Which of these graphs is always bipartite?

    A tree has no cycles, so it has no odd cycle; color vertices by the parity of their depth. A triangle (K3), self loops and odd cycles break the property.
  5. 5. Greedy graph coloring uses 3 colors on a path when the vertex order is unlucky. What does this show?

    A path can always be colored with 2 colors, but greedy coloring may use more if vertices are processed in a bad order.

Summary

  • A graph is bipartite if its vertices split into two groups with every edge between the groups, which is the same as having a valid 2-coloring.
  • The odd-cycle rule: a graph is bipartite if and only if it has no cycle of odd length. Trees and even cycles are bipartite; triangles and 5-cycles are not.
  • BFS (or DFS) 2-coloring tests it in O(V + E): color a neighbor with the opposite color, and report failure if an edge joins two vertices of the same color. Start from every uncolored vertex.
  • Possible bipartition (splitting people who dislike each other) is the same check; brute force over all splits is O(2^n).
  • Bipartite matching assigns left vertices to right vertices; Kuhn's augmenting-path algorithm finds a maximum matching in O(V x E), where greedy may get stuck.
  • Coloring with 3 or more colors is NP-complete; greedy coloring is a quick heuristic whose result depends on the vertex order.

Next: Union-Find (Disjoint Sets)