Bipartite Check

A graph is bipartite when its vertices can be split into two groups with every edge crossing between the groups, never inside one. Checking bipartiteness is equivalent to testing whether the graph can be colored with two colors, or whether it contains no odd-length cycle.

How it works

A BFS or DFS traversal 2-colors the graph on the fly: color the start vertex, then give every discovered neighbor the opposite color. If an edge ever connects two vertices of the same color, an odd cycle exists and the graph is not bipartite. Every component must be checked. The test runs in O(V + E) time.

Applications

Bipartite structure underlies matching problems: assigning students to schools, jobs to machines, and riders to drivers. Recommender systems model users and items as the two sides of a bipartite graph. The odd-cycle characterization is a frequent interview warm-up that leads into maximum matching topics.