How do you check if a graph is bipartite? | Interview Question

Q: How do you check if a graph is bipartite?

**Target Audience:** Beginners preparing for coding interviews — you know Python lists and loops; graphs and colouring are explained from scratch. **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with `python3` (3.13); nothing is typed in by hand. ## 1. Why This Even Matters — A Story First A teacher wants to split a class into **two teams** for a quiz. There is one rule: some pairs of students are rivals, and rivals must be on **different** teams. Can it be done? Try it with four students in a ring of rivalries: Ana–Ben, Ben–Cy, Cy–Dee, Dee–Ana. Put Ana on Red. Then Ben must be Blue, so Cy must be Red, so Dee must be Blue — and Dee–Ana is Blue–Red, fine. It works. Now three students who are all rivals: Ana–Ben, Ben–Cy, Cy–Ana. Ana is Red, Ben is Blue, C

The problem

Question presented to candidate: "You are given an undirected graph as an adjacency list — graph[u] is the list of nodes joined to u. Return whether the graph is bipartite: can you split the nodes into two groups so that every edge goes between the groups? The graph may be disconnected. Please write it in Python."

What a strong answer should cover:

The reformulation: bipartite ⇔ the graph can be 2-coloured ⇔ it has no odd cycle.
BFS (or DFS) colouring: give each uncoloured neighbour the opposite colour; a neighbour with the same colour means False.
An outer loop over every node so each connected component gets its own traversal.
O(V + E) time and O(V) extra space, plus the free result: the colour array is the two sides.
Python specifics: collections.deque with popleft() for the queue, building adjacency lists with a list comprehension (never [[]] * n), and recursion depth limits if you write the DFS recursively.

Clarifying questions expected:

Can the graph be disconnected or contain self-loops?
Do you need only the yes/no answer, or the two groups too?

Code / implementation expected: Yes — an is_bipartite(graph) function in Python with a colour list and BFS, tested on a bipartite graph, a triangle and a disconnected graph.

graphs
bfs
coloring

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you know Python lists and loops; graphs and colouring are explained from scratch. Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown was produced by actually running the code with python3 (3.13); nothing is typed in by hand.

1. Why This Even Matters — A Story First

A teacher wants to split a class into two teams for a quiz. There is one rule: some pairs of students are rivals, and rivals must be on different teams. Can it be done?

Try it with four students in a ring of rivalries: Ana–Ben, Ben–Cy, Cy–Dee, Dee–Ana. Put Ana on Red. Then Ben must be Blue, so Cy must be Red, so Dee must be Blue — and Dee–Ana is Blue–Red, fine. I

The solution is hidden so you can try first

14 min read · 10 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonBFS 2-colouring on eight graphs, printing both sides when it succeeds

Practice

PythonBFS vs iterative DFS vs union-find agree on 500 random graphs

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.