Bipartite Graphs — Graph Theory

Overview

What this concept solves

A bipartite graph is one whose vertices split into two groups, with every edge crossing between the groups and never staying inside one. Picture two columns of dots: edges only ever run left-to-right, never left-to-left or right-to-right. The two groups are often called the two sides, parts, or colours — and that last word is the key, because a graph is bipartite exactly when you can paint its vertices in two colours so that no edge ever joins two vertices of the same colour.

This is the natural model whenever the things you're connecting fall into two distinct kinds and relationships only ever cross the divide. Students and the courses they enrol in, jobs and the machines that can run them, buyers and sellers, actors and films, people and the events they attend. In each case an edge says 'this thing on the left relates to this thing on the right' — and two things on the same side are never directly joined.

The deep fact is a three-way equivalence: a graph is bipartite if and only if it is 2-colourable if and only if it contains no odd-length cycle. That last clause is the one to internalise. A triangle (a 3-cycle) is the smallest thing that can't be 2-coloured — colour two of its vertices and the third is adjacent to both, so it has no legal colour. Any odd cycle traps you the same way. Even cycles are fine; they alternate colours and close up cleanly. So testing bipartiteness is just a hunt for an odd cycle, and a single BFS or DFS finds one (or proves there's none) in linear time.

Mechanics

How it works

The pieces

Two parts (sides) — the vertex set splits into V = X ∪ Y with X and Y disjoint. Group 0 and group 1, left and right, the two colours — same idea, different names.
Crossing edges only — every edge has one endpoint in X and one in Y. No edge lives wholly inside X or wholly inside Y.
2-colouring — assign each vertex one of two colours so adjacent vertices always differ. The colour classes are the two parts.
Odd cycle — a cycle with an odd number of edges (a triangle, a pentagon). Its presence is the exact obstruction to bipartiteness.

Testing it with a BFS 2-colouring

Pick any unvisited vertex, paint it colour 0, and put it in a queue.
Dequeue a vertex u. For each neighbour v: if v is uncoloured, paint it the opposite colour of u and enqueue it.
If v is already coloured the same as u, stop — you've found an edge inside one colour class, so the graph is not bipartite (you've just walked an odd cycle).
Repeat until the queue empties; restart from any still-uncoloured vertex to cover every component.
If you colour everything with no conflict, the two colour classes are the two sides — the graph is bipartite.

Why an odd cycle is fatal

Walk around a cycle alternating colours: 0, 1, 0, 1, … To close the loop, the last vertex must differ from the first. That works only if the number of steps is even. An odd cycle forces the last vertex to share the start's colour while being adjacent to it — an impossible demand. Even cycles alternate perfectly and close with no clash, which is why they're harmless.

Two sides need not be equal

Bipartite says nothing about the two parts being the same size. A star (one centre joined to n leaves) is bipartite with parts of size 1 and n. The prototype's default graph happens to be a balanced 3 + 3, but 2 + 4 or 1 + 5 would be just as bipartite.

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

simulation › Bipartite Graphs

About this simulation

A six-vertex graph across four tabs. Two-colour it runs a BFS that paints each vertex the opposite colour of its neighbour on a clean bipartite graph; An odd cycle breaks it runs the same process on a graph with a triangle and stops at the edge that demands two same-coloured vertices; Split into two sides rearranges the bipartite graph into two columns so every edge visibly crosses the gap. Free play lets you click two vertices to toggle an edge, drag vertices around, and hit Test bipartite to 2-colour whatever you built — the group sizes and the bipartite? verdict update live.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Two-colour it

On Two-colour it, press Play. A BFS starts at vertex A, paints it group 0 (blue), and fans outward — every neighbour it reaches gets painted the opposite colour. Watch the warning-coloured edge as each one is checked: every edge joins a blue vertex to a purple one, so none ever clashes. The final step reports success and the two group sizes; the side panel lists the members of group 0 and group 1. Use Step / Back to crawl one colouring at a time.

try 02

An odd cycle breaks it

Switch to An odd cycle breaks it and Play. This graph hides a triangle. The 2-colouring proceeds happily until it reaches an edge whose two endpoints have already been painted the same colour — that edge flashes red as the conflict. The narration spells out the odd cycle you just walked: there's no way to 2-colour a triangle, so the graph is not bipartite. The side panel pins down exactly which edge broke it.

try 03

Split into two sides

On Split into two sides, Play to watch the bipartite graph rearrange itself. The vertices slide into two clean columns — group 0 on the left, group 1 on the right — and once they settle, every edge visibly crosses the gap from left to right. None stays within a column. That picture is the definition of bipartite made literal; the side panel names the left and right members.

try 04

Free play — build and test your own

Open Free play. Click any two vertices to toggle an edge between them; drag vertices to rearrange. When you're ready, hit Test bipartite to run the 2-colouring on whatever you built — the bipartite? stat turns green for Yes or red for No, and the group-sizes stat fills in. Try adding an edge that closes a triangle and watch the verdict flip to No; remove it and it flips back. Clear edges strips everything; Reset graph restores the starting layout.

In practice

When to use it — and what you give up

Model it as bipartite when

Your entities fall into two distinct kinds and edges only cross — users and items, students and courses, jobs and machines, applicants and slots.
You need a matching — assigning workers to tasks, residents to hospitals, or ads to slots is the classic bipartite matching problem, solvable in polynomial time precisely because the graph is bipartite.
You're building a recommender or two-mode network — buyer–product and reader–article graphs are bipartite by construction, and projecting onto one side reveals 'who shares interests'.

Reach for a general graph instead when

Same-kind vertices connect directly — if friends (one kind) link to friends, you have odd cycles and the bipartite structure is gone.
The graph already contains a triangle or any odd cycle — it simply isn't bipartite, and forcing the model will mislead you.
You need more than two groups — proper colouring with three or more colours, or k-partite structure, is a different (and generally much harder) problem.

Pros

Cheap to verify — a single BFS/DFS 2-colouring decides bipartiteness in O(V + E) and hands you the two sides for free.
Matching becomes tractable — maximum matching, which is NP-hard intuitions aside, is polynomial on bipartite graphs (Hopcroft–Karp in O(E√V)).
Natural fit for two-kind data — users/items, jobs/machines, and similar domains map onto it with zero distortion.
Clean visual structure — laying the two sides in two columns makes every relationship a crossing edge, instantly readable.

Cons

A single odd cycle destroys it — add one triangle and the whole graph is no longer bipartite; the property is fragile.
Only two groups — anything needing three or more categories falls outside the model.
Can't express same-side links — a real friendship between two users (same side) has no place in a user–item bipartite graph.
Projections lose information — collapsing a bipartite graph onto one side to get 'shared interests' discards which item created each link.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

bipartite-graph.ts

// Test whether an undirected graph is bipartite by 2-colouring it
// with a BFS. Returns the two sides on success, or null if an odd
// cycle is found (i.e. the graph is not bipartite).
function bipartition(
  adj: Map<string, string[]>,
): [string[], string[]] | null {
  const colour = new Map<string, 0 | 1>();

  for (const start of adj.keys()) {
    if (colour.has(start)) continue;        // already handled this component
    colour.set(start, 0);
    const queue: string[] = [start];

    while (queue.length > 0) {
      const u = queue.shift()!;
      const next = (colour.get(u)! ^ 1) as 0 | 1;   // opposite colour
      for (const v of adj.get(u) ?? []) {
        if (!colour.has(v)) {
          colour.set(v, next);              // paint neighbour the other colour
          queue.push(v);
        } else if (colour.get(v) === colour.get(u)) {
          return null;                      // same colour across an edge → odd cycle
        }
      }
    }
  }

  // No conflicts: the two colour classes are the two sides.
  const side0: string[] = [], side1: string[] = [];
  for (const [v, c] of colour) (c === 0 ? side0 : side1).push(v);
  return [side0, side1];
}

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Which condition is exactly equivalent to a graph being bipartite?

question 02 / 03

While 2-colouring a graph with BFS, you reach an edge whose two endpoints are already painted the same colour. What does this prove?

question 03 / 03

Why is a triangle (a 3-cycle) the smallest graph that is not bipartite?

0/3 answered