## DEV Community is a community of 891,862 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

JB

Posted on • Updated on

# Checking If An Undirected Graph Is Bipartite

2021/01/05 - The previous C# code sample implemented the algorithm incorrectly. A corrected Java implementation has been added in its place.

If you are unfamiliar with graphs, check out some of my earlier posts on them.

## Resources:

Takeaways:

• A bipartite graph (bigraph) is a graph where the vertices can be divided into two disjoint, independent, sets `u` and `v`. Every edge will connect a vertex from one set to the other (without self referencing edges - I.E edges going from a vertex in `u` to another vertex in `u`).
• One way to visualize a bipartite graph, is to colour all the vertices in a set the same colour. Set `u` could be red vertices, whereas `v` could be black. This would mean an edge would always consist of a red and black pair of vertices.
• This type of two-colouring is impossible in non-bipartite graphs. Think of a graph with three vertices arranged in a triangle. We cannot represent this graph as two independent sets, and we cannot two-colour it in such a way that will allow each edge to have different coloured endpoints.
• One way in which we can check if a graph is bipartite, is to run a depth-first search (DFS) over the vertices. Applying two colouring to the graph.
• Start at a random vertex `v` and colour it colour1 (red, for example).
• Colour all adjacent vertices `u` the opposite colour of `v`. For each adjacent `u`, also recursively call our DFS routine.
• If a graph is bipartite, we can complete this two-colouring without a contradiction.
• If the graph is not bipartite, then at some point a vertex will get both colours - and this contradiction means we cannot achieve a two-colouring of the graph.
• Time complexity is `O(v + e)` for an adjacency list. Space complexity is `O(v)`. For an adjacency matrix, the time & space complexity would be `O(v^2)`.

Undirected graph that can be two-coloured:

Undirected graph that cannot be two-coloured:

Below are implementations for checking if undirected graphs are bipartite. There is solutions for both undirected adjacency list & adjacency matrix representations of graphs:

As always, if you found any errors in this post please let me know!