Bipartite graphs

Overview

A graph is bipartite when its vertices divide into two groups such that every edge goes between the groups, never within one — equivalently, it can be coloured with two colours so no edge joins same-coloured vertices. A BFS/DFS assigns alternating colours; a conflict (an edge between two equally-coloured vertices) proves the graph is not bipartite.

Why it matters

Bipartite structure models 'two kinds of things related across the divide': jobs and applicants, students and courses, users and items. Bipartite graphs enable matching algorithms, and the 2-colouring test is the classic way to detect an odd cycle.

Core concepts

2-colouring. Colour a start vertex 0, its neighbours 1, theirs 0, alternating outward.

Odd-cycle obstruction. A graph is bipartite iff it contains no odd-length cycle; the colour clash is exactly where an odd cycle closes.

All components. Restart the colouring on every uncoloured vertex — the graph is bipartite only if every component is.

Why odd cycles are the only obstruction. Walking around any cycle the colours must alternate; an even cycle returns to the start with the original colour, but an odd one arrives back with the opposite, which is a contradiction. So a graph is bipartite precisely when it contains no odd cycle — the colour clash the algorithm detects is exactly that contradiction surfacing.

Syntax notes

#include <stdlib.h>

/* 2-colour every component; 0 and 1 are the two sides, -1 = uncoloured */
int is_bipartite(const int *adj, int n) {
    int *col = malloc((size_t)n * sizeof *col);
    int *q   = malloc((size_t)n * sizeof *q);
    if (!col || !q) { free(col); free(q); return -1; }
    for (int i = 0; i < n; i++) col[i] = -1;
    int ok = 1;
    for (int s = 0; s < n && ok; s++) {          /* EVERY component, not just vertex 0 */
        if (col[s] != -1) continue;
        int head = 0, tail = 0;
        col[s] = 0; q[tail++] = s;
        while (head < tail && ok) {
            int v = q[head++];
            for (int u = 0; u < n; u++)
                if (adj[v*n + u]) {
                    if (col[u] == -1) { col[u] = 1 - col[v]; q[tail++] = u; }
                    else if (col[u] == col[v]) { ok = 0; break; }   /* odd cycle */
                }
        }
    }
    free(col); free(q);
    return ok;
}

Key points:

• 1 - col[v] flips between the two colours.
• The outer loop over s is essential: a graph is bipartite only if every component is.
• A same-coloured neighbour is exactly an odd cycle — the only obstruction to bipartiteness.

Lesson

A graph is bipartite if its vertices split into two sets with every edge crossing between them — equivalently, it is 2-colourable. BFS/DFS alternates colours as it walks; a neighbour that already carries the current vertex's colour reveals an odd cycle, the exact obstruction to bipartiteness. Disconnected graphs must be checked component by component.

Code examples

#include <stdio.h> int main(void){ int n=4; /* a 4-cycle 0-1-2-3-0 : bipartite / int adj[16]={ 0,1,0,1, 1,0,1,0, 0,1,0,1, 1,0,1,0 }; int color[4]={-1,-1,-1,-1}, q[4], head=0,tail=0, ok=1; color[0]=0; q[tail++]=0; while(head<tail&&ok){ int v=q[head++]; for(int u=0;u<n;u++) if(adj[vn+u]){ if(color[u]<0){ color[u]=1-color[v]; q[tail++]=u; } else if(color[u]==color[v]) ok=0; } } printf("bipartite? %s\n", ok?"yes":"no"); if(ok) for(int i=0;i<n;i++) printf("vertex %d -> set %d\n", i, color[i]); return 0; }

Line by line

Common mistakes

Checking only the component containing vertex 0 and ignoring the rest. Concluding 'bipartite' as soon as one component works. Confusing 'has no edges' (trivially bipartite) with an error case.

Debugging tips

Compiler errors and warnings:

• -Wmaybe-uninitialized if col is malloced without the -1 fill.
• No warning for checking only one component.

Runtime symptoms:

• A disconnected non-bipartite graph reports bipartite. You only coloured the component containing vertex 0. Sweep every uncoloured vertex.
• Everything reports non-bipartite. You compared against the wrong vertex's colour, or used != where == was meant.
• Crash or wrong colours. col was zero-initialised, so vertices look pre-coloured as side 0. The sentinel must be -1.
• Queue overflow. A vertex was enqueued more than once because it was coloured too late — colour it at enqueue time.
• An odd cycle is missed. You stopped at the first component that succeeded instead of continuing.

Technique: test an even cycle (bipartite), an odd cycle (not), a tree (always bipartite), and a graph whose second component contains a triangle — the last one catches the single-component bug.

Memory safety

• Sentinel must be -1. With calloc, every vertex reads as already coloured 0, which both breaks the algorithm and skips the enqueue that keeps the queue sized correctly.
• Colour at enqueue. As in BFS, colouring late allows a vertex to be pushed twice and overflow the n-slot queue — a real out-of-bounds write.
• Two allocations, one failure path. Check both and free whatever succeeded.
• Undirected precondition. Bipartiteness is defined for undirected graphs; running this on an asymmetric matrix silently answers a different question.
• No recursion, so no stack-depth concern — an advantage over a DFS colouring on large graphs.
• Free on every path, including the early failure return.

Real-world uses

Concrete uses: Bipartite structure models two-sided relationships — students and courses, jobs and applicants, users and items, tasks and machines — and detecting it is the precondition for bipartite matching algorithms (Hopcroft-Karp) used in assignment problems. Two-colourability is also the simplest case of graph colouring, which underlies register allocation and scheduling; and the odd-cycle test is used in checking consistency of constraint systems where relations must alternate.

Professional best practices:

Beginner:

• Always sweep every component.
• Use -1 for uncoloured so 0 remains a valid side.

Intermediate:

• When the answer is "not bipartite", report the offending odd cycle — it is the actionable diagnostic.
• Keep the colour array afterwards: it is the partition, and downstream matching algorithms need it.
• BFS colouring is usually preferable to DFS here because it avoids deep recursion on large graphs.

Practice tasks

1. (Beginner) Bipartite test. Implement is_bipartite covering all components. Example: a 4-cycle -> 1; a triangle -> 0. Concepts: 2-colouring, component sweep.

2. (Beginner) Validate a colouring. Implement int is_valid_coloring(const int *adj, int n, const int *color) returning 0 if any edge joins two equal colours. Concepts: checking a constraint directly.

3. (Intermediate) Report the partition. Return the two vertex sets when the graph is bipartite. Concepts: the colour array as output.

4. (Intermediate) Find the odd cycle. When the test fails, print the cycle that caused it. Hint: keep a parent array and walk both endpoints back to their common ancestor. Concepts: diagnostics.

Summary

A graph is bipartite exactly when it can be 2-coloured so no edge joins two vertices of the same colour — equivalently, when it contains no odd cycle. BFS assigns a start vertex to side 0 and every neighbour the opposite side with 1 - col[v]; encountering an already-coloured neighbour with the same colour is the odd cycle that proves bipartiteness impossible. The two details that matter are sweeping every component (a graph is bipartite only if all of them are) and using -1 rather than 0 for "uncoloured", since 0 is a real side. Colour vertices as you enqueue them so the queue cannot overflow, and keep the colour array — it is the partition itself.

Practice with these exercises

• Is the graph bipartite?
• Validate a coloring