Interactive Graph Theory Learning
Interactive Graph Theory Learning
Guest User
Using app without sign in
Bipartite graph checker
Determines if graph can be colored with two colors
Select an algorithm and generate steps to begin visualization
A graph is bipartite when its vertices can be split into two groups with every edge crossing between the groups, never inside one. Checking bipartiteness is equivalent to testing whether the graph can be colored with two colors, or whether it contains no odd-length cycle.
A BFS or DFS traversal 2-colors the graph on the fly: color the start vertex, then give every discovered neighbor the opposite color. If an edge ever connects two vertices of the same color, an odd cycle exists and the graph is not bipartite. Every component must be checked. The test runs in O(V + E) time.
Bipartite structure underlies matching problems: assigning students to schools, jobs to machines, and riders to drivers. Recommender systems model users and items as the two sides of a bipartite graph. The odd-cycle characterization is a frequent interview warm-up that leads into maximum matching topics.
A graph is bipartite exactly when it can be two-coloured. So the test is a traversal that colours each vertex opposite to its parent and watches for a clash.
isBipartite(graph):
color = {} for all vertices
for each vertex s with no color: // every component
color[s] = 0
queue = [s]
while queue is not empty:
u = queue.pop()
for each neighbor v of u:
if v has no color:
color[v] = 1 - color[u]
queue.push(v)
else if color[v] == color[u]:
return false // odd cycle found
return trueThe clash is not an arbitrary failure signal, it is a proof. If two adjacent vertices receive the same colour, the tree paths from them back to their common ancestor plus the connecting edge form a cycle of odd length. Bipartite graphs are exactly the graphs with no odd cycle, so the conflict edge is a certificate you can hand back to the caller.
Two-colour a four-cycle, then add one chord and watch the same traversal reject it.
Example graph: First a 4-cycle A-B, B-C, C-D, D-A. Then the same graph with the chord A-C added.
The 4-cycle is bipartite with parts {A, C} and {B, D}; adding the chord A-C makes it non-bipartite, detected at edge B-C. Note the general rule this illustrates: every even cycle is bipartite and every odd cycle is not, so cycle length alone decides it. Note also that the conflict was reported on edge B-C rather than on the chord itself, which is normal, since the algorithm reports wherever the contradiction first surfaces, not the edge you would blame.
Time: O(V + E) · Space: O(V)
This is a single BFS or DFS with one comparison per edge, so it costs exactly one traversal. Every vertex is coloured once and every edge is inspected once from each endpoint. Space is one colour per vertex plus the queue or recursion stack, both O(V). The loop over all vertices adds nothing asymptotically and is what makes disconnected graphs work. There is no faster approach, since deciding bipartiteness requires looking at every edge: a single unexamined edge could be the one creating an odd cycle.
Bipartiteness is usually a precondition rather than a goal. What you do next depends on why you asked.
| Alternative | Prefer it when | Cost |
|---|---|---|
| Hopcroft-Karp | The graph is bipartite and you now want a maximum matching between the two parts. | O(E·sqrt(V)) |
| Graph colouring | The graph is not bipartite and you need the actual chromatic number, which is 3 or more. | NP-hard in general |
| Odd cycle detection | You want the offending cycle itself, not just a yes or no. Reconstruct it from the BFS parent pointers at the conflict edge. | O(V + E) |
| Union-Find with parity | Edges arrive incrementally and you want to reject the first one that breaks bipartiteness as it is added. | O(E·α(V)) |
Read the full article: Graph Algorithms in Coding Interviews
Related algorithms: Breadth-First Search, Graph Coloring, Maximum Flow