Bipartite check by two-coloring in Python

Why this matters

Many problems ask you to split a set of things into two groups. Two teams for a match. Two rooms for a meeting. Two shifts for a rota. Often there is a rule: some pairs must be in different groups. Two people who dislike each other cannot share a room. Two players who are rivals cannot be on the same team.

You can model this as a graph. Each person is a vertex (a point in the graph). Each rule "these two must be apart" is an edge (a link between two vertices). The question becomes: can every vertex get one of two colours so that no edge joins two vertices of the same colour? A graph with this property is called bipartite. "Bi" means two, and "partite" means parts. The check that finds the two colours is called two-coloring.

This lesson shows how to run the check with a queue (breadth-first search, BFS) and with recursion (depth-first search, DFS). It also explains why a failed check proves that no valid split exists. The graph lessons earlier in this module cover the basic walks. This lesson uses them for one job.

Words used in this lesson

• Edge: a link between two vertices. Here it means "these two must end up in different groups".
• Colour: a label on a vertex. There are two colours, 0 and 1. A colour is just a group name.
• Cycle: a walk that starts and ends at the same vertex without repeating a vertex in between. The number of edges in a cycle is its length.
• Odd cycle: a cycle whose length is odd, such as 3 or 5.
• Component: a part of a graph whose vertices can all reach each other. A graph can have several components that do not touch.
• Uncoloured: a vertex that has no colour yet. The code marks it with -1.

The idea with a small example

Take three people, Asha, Ben and Chen. Each pair has a rule that they must be in different rooms. So the edges are Asha to Ben, Ben to Chen and Chen to Asha. In a picture, the three people form a triangle.

Try to colour them. Give Asha colour 0. Ben must differ from Asha, so Ben gets colour 1. Chen must differ from Ben, so Chen gets colour 0. But Chen also must differ from Asha, and Asha is colour 0. The rule is broken. No colouring works, so there is no valid split into two rooms.

Now take four people in a square: Asha to Ben, Ben to Chen, Chen to Dana and Dana to Asha. Give Asha colour 0. Ben gets 1, Chen gets 0, and Dana gets 1. Dana is joined to Asha, which is 0, so the colours differ. Every edge joins different colours. The two rooms are {Asha, Chen} and {Ben, Dana}.

The difference between the triangle and the square is the length of the loop. The triangle has three edges, and the square has four. A loop with an odd number of edges cannot be coloured with two colours. Each step along the loop flips the colour, so an odd loop flips an odd number of times and comes back to a different colour than it started. The rest of this lesson turns that observation into a method.

The method

Pick any uncoloured vertex, give it colour 0, and walk outward. When you visit a neighbour:

1. If the neighbour has no colour yet, give it the opposite colour and continue the walk from it.
2. If the neighbour already has the opposite colour, leave it alone.
3. If the neighbour already has the same colour as the current vertex, you have found a conflict. The answer is no.

If every vertex is coloured and no conflict appears, the answer is yes.

A graph can have several components. Each component needs its own start, because a walk from one component cannot reach another. So the outer loop tries every vertex, and starts a new walk whenever it finds an uncoloured one.

The BFS version

The BFS version uses a queue. It visits vertices in rounds, so each vertex is handled after the vertices closer to the start.

In Python, the queue is a deque (short for double-ended queue) from the collections module. append adds an item to the back, and popleft removes the item at the front. A plain list also works, but list.pop(0) gets slower as the list grows, because Python moves every remaining item one place to the left. A deque takes the same time to remove from the front, however long the queue is.

while queue: repeats as long as the queue has items. An empty deque counts as false in a while or if, so the loop stops on its own.

Here is the complete Python program. It contains the BFS check, the DFS check (shown next), and the examples used in this lesson. The program needs nothing from the user, so you can run it as it is.

Save the file as bipartite.py and run it with python3 bipartite.py. The output was produced with Python 3.14.4:

Triangle (BFS): False
Triangle (DFS): False
Four-cycle (BFS): True
Four-cycle (DFS): True
Edge plus triangle: False
Self-loop: False
Possible bipartition, example 1: True
Possible bipartition, example 2: False

Read the two_colour function line by line. The for loop over start covers every component. The while loop is the walk. The line color[v] = 1 - color[u] flips the colour, because 1 minus 0 is 1 and 1 minus 1 is 0. The elif line is the conflict check. It runs for every neighbour that is already coloured, so every edge is checked from at least one end. The function returns None on a conflict, and the list of colours otherwise. None is Python's built-in value for "no result", so it marks the failure case. is_bipartite only asks whether the result is not None.

The DFS version

DFS uses recursion instead of a queue. Recursion means a function that calls itself. The walk goes as deep as it can along one path before it backs up. The colouring rule is the same, so the code is short. This is the paint function in the program above:

def paint(graph, color, u, c):
    color[u] = c
    for v in graph[u]:
        if color[v] == -1:
            if not paint(graph, color, v, 1 - c):
                return False
        elif color[v] == c:
            return False
    return True

The function colours u with c, then tries each neighbour v. An uncoloured neighbour gets the opposite colour, and the walk continues from it. A neighbour with the same colour c is the conflict. Both versions give the same answer on every graph. Pick the one you find easier to read.

The recursion has a limit in Python. By default, Python stops after 1000 nested calls. sys.getrecursionlimit() returns that number, and it printed 1000 on the machine used for this lesson. A walk that goes deeper than the limit raises RecursionError. BFS does not use the call stack, so it has no such limit. For a long chain of vertices, BFS is the safer choice.

Why the answer is trustworthy

The method gives two kinds of answer, and each has a short proof.

When the method says yes

The method says yes only if it finishes without a conflict. Then every vertex has a colour. Every edge was checked from at least one end, and each check found the two colours different. So the colouring is valid, and the two groups are the colour 0 vertices and the colour 1 vertices.

This is a proof by checking. Once the method ends without a conflict, you can read the colours and confirm each edge yourself.

When the method says no

The method says no when it finds a neighbour with the same colour as the current vertex. Here is why that proves no split exists.

Look at the walk that led to the conflict. Each step along the walk flips the colour. The start has colour 0, so a vertex reached after k steps has colour k mod 2 (the remainder after dividing k by 2). That means colour 0 for even k and colour 1 for odd k.

The conflict edge joins two vertices with the same colour. Call them p and q. Both were reached by walks of the same parity (both even or both odd), so the number of steps to p and to q is even, or both are odd. Put them together with the conflict edge, and you have a closed walk back to the start. Its length is the steps to p, plus the steps to q, plus 1 for the conflict edge. Two numbers of the same parity add up to an even number, and adding 1 makes it odd. So the closed walk has odd length. A closed walk of odd length always contains an odd cycle, so the graph has an odd cycle.

A graph with an odd cycle cannot be split into two groups with every edge crossing between them. Walk around the odd cycle: each edge must switch groups, so after an odd number of edges you are back where you started but in the other group. That is a contradiction. So the answer no is correct.

Worked example 2: groups on a path

The second example shows the actual groups. Take a path of five vertices: 0 to 1, 1 to 2, 2 to 3, and 3 to 4. Each vertex is connected to the next. This is like a line of five people who each dislike only their neighbour in the line.

Build the path and print its colours with two_colour:

path = new_graph(5)
for a in range(4):
    add_edge(path, a, a + 1)
print("Path colours:", two_colour(path))

Path colours: [0, 1, 0, 1, 0]

Vertices 0, 2 and 4 have colour 0, so they form one group. Vertices 1 and 3 have colour 1, so they form the other group. Every edge joins a 0 and a 1, so the split works.

The same method on a square gives [0, 1, 0, 1]. The two groups are {0, 2} and {1, 3}.

A graph with two components, such as an edge from 0 to 1 and a path from 2 to 4, gives [0, 1, 0, 1, 0]. The list has five entries because the graph has five vertices. Each component starts with colour 0. That choice is arbitrary. Swapping the colours inside one component gives another valid split. This matters when a problem counts the splits. For a yes or no answer, it does not matter.

Worked example 3: possible bipartition

LeetCode problem 886 "Possible Bipartition" is a classic two-group question. There are n people, numbered 1 to n. You get a list of pairs who dislike each other. The task is to decide whether the people can be split into two groups so that nobody is in the same group as someone they dislike.

The translation is direct. Each person is a vertex, each dislike pair is an edge, and the answer is is_bipartite on that graph.

def possible_bipartition(n, dislikes):
    graph = new_graph(n + 1)
    for a, b in dislikes:
        add_edge(graph, a, b)
    return is_bipartite(graph)

The people are numbered from 1, but Python lists start at 0 as well. The code creates n + 1 slots, so the vertex numbers 1 to n all fit. Slot 0 is never used. It has no edges, so the method gives it a colour and moves on.

Two examples from the problem:

• With 4 people and dislikes (1, 2), (1, 3) and (2, 4), the answer is True. Person 1 goes in one group, persons 2 and 3 in the other, and person 4 with person 1.
• With 3 people and dislikes (1, 2), (1, 3) and (2, 3), the answer is False. The three form a triangle, so there is no split.

The program prints True and False for these two cases, as shown above. Python writes booleans with a capital letter, so the output reads True and False.

Common mistakes

Checking only one start vertex

A common mistake is to colour from vertex 0 and stop. The walk from vertex 0 covers only its own component. A conflict in another component goes unnoticed. Here is a version of the check that does that:

def check_only_vertex_zero(graph):
    color = [-1] * len(graph)
    color[0] = 0
    queue = deque([0])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if color[v] == -1:
                color[v] = 1 - color[u]
                queue.append(v)
            elif color[v] == color[u]:
                return False
    return True

Run it on a graph with two parts, an edge from 0 to 1 and a triangle on 2, 3 and 4. Add this code after the function above:

graph = new_graph(5)
add_edge(graph, 0, 1)
add_edge(graph, 2, 3)
add_edge(graph, 3, 4)
add_edge(graph, 4, 2)
print("Only vertex 0 checked:", check_only_vertex_zero(graph))
print("All components checked:", is_bipartite(graph))

The first line is wrong:

Only vertex 0 checked: True
All components checked: False

The triangle is never visited, so the wrong answer True comes back. The fix is the outer for loop in two_colour.

Mixing up the vertex numbers

If the problem numbers people from 1, and the code makes a graph with n slots, then vertex n does not exist. The error appears as soon as an edge uses that number. Calling add_edge on a graph with 4 slots and the edge (0, 4) gives this:

Traceback (most recent call last):
  File "<string>", line 4, in <module>
    add_edge(bad, 0, 4)
    ~~~~~~~~^^^^^^^^^^^
  File "...bipartite.py", line 10, in add_edge
    graph[b].append(a)
    ~~~~~^^^
IndexError: list index out of range

The directory part of the file path depends on where you save the file. The last line names the error. Python does not show the index or the list length in this message, so read the line number in the traceback and check the value you passed. The fix is to make n + 1 slots, as shown in possible_bipartition. Alternatively, subtract 1 from each vertex number when you read the input.

Treating a self-loop as harmless

A self-loop is an edge from a vertex to itself, such as 0 to 0. Someone might think it cannot break anything. But the vertex is its own neighbour, so when it is coloured, the check sees a neighbour with the same colour and returns None. The answer is correct. A self-loop is a cycle of length 1, which is odd. If a problem says a person cannot be in the same group as themselves, the answer is no.

Using 0 to mean uncoloured

Some people set the colour list to 0 at the start, instead of -1. Then an unvisited vertex looks coloured, so the code never gives it a colour of its own and compares it with the colour it should have had. Use a value that is neither 0 nor 1 to mean uncoloured. The code above uses -1, and it checks color[start] != -1 before it starts a new walk.

Practice

Exercise 1: draw the groups

Take the graph with vertices 0 to 5 and edges 0 to 1, 1 to 2, 2 to 3, 3 to 4, 4 to 5 and 5 to 0. Is it bipartite? If yes, give the two groups.

Show the answer

Yes. It is a cycle of six edges, which is even. Starting from 0 with colour 0, the colours are 0, 1, 0, 1, 0, 1 for vertices 0 to 5. The groups are {0, 2, 4} and {1, 3, 5}. Every edge joins a 0 and a 1.

Exercise 2: find the odd loop

Take the graph with vertices 0 to 4 and edges 0 to 1, 1 to 2, 2 to 0 and 3 to 4. Is it bipartite? Name the reason in one sentence.

Show the answer

No. The vertices 0, 1 and 2 form a triangle, which is an odd loop. The edge from 3 to 4 is fine on its own, but the triangle alone is enough to make the whole graph fail.

Exercise 3: possible bipartition

There are 5 people. The dislike pairs are 1 with 2, 2 with 3, 3 with 4, and 4 with 1. Can the people be split into two groups with no dislike pair inside a group? Explain using the cycle.

Show the answer

Yes. The dislikes form the loop 1, 2, 3, 4, 1, which has four edges, so it is even. Person 5 has no dislikes and can go in either group. Give person 1 colour 0, person 2 colour 1, person 3 colour 0 and person 4 colour 1. Person 4 is then joined to person 1, which is 0 and differs from 4's colour 1. The answer is True.

Exercise 4: why the start colour does not matter

A teammate says you must always give the start vertex colour 0. Is this a rule for the method to be correct?

Show the answer

No. Colour 0 is only a name. If the start gets colour 1, every other colour is flipped, but every edge still joins different colours. The split is the same two groups with their labels swapped. The method is correct either way. The choice matters only when a problem asks for a particular group label.

Exercise 5: the number of splits

Suppose a connected graph is bipartite. How many different ways are there to split its vertices into two groups, counting the groups as unlabelled? Give the answer in terms of the start choice.

Show the answer

There are 2 ways if you count the groups as labelled, and 1 way if you count them as an unordered pair. Once the colour of one vertex is fixed, the colour of every other vertex in a connected graph is forced, because each step flips the colour. So the split is determined by the start choice. Choosing colour 0 or colour 1 for the start gives the two labelled splits. Counting the unordered pair gives one.

Summary

• Two-coloring gives each vertex one of two colours so that every edge joins different colours. A graph where this works is bipartite.
• BFS and DFS both run the same check. Start a new walk for each uncoloured vertex so every component is covered.
• A conflict means an odd loop exists, and an odd loop proves that no two-group split is possible.
• Model two-group problems by making each person a vertex and each "must be apart" rule an edge.