Splitting into two sides
A graph is bipartite when its vertices can be divided into two groups such that every edge connects a vertex in one group to a vertex in the other, never within the same group. Bipartite graphs model matchings, schedules, and many two sided relationships.
Two coloring
You can test bipartiteness with a search that assigns one of two colours to each vertex:
- Colour a starting vertex, say group one.
- During BFS or DFS, give every neighbour the opposite colour of the current vertex.
- If you ever reach a neighbour that already carries the same colour as the current vertex, the graph cannot be bipartite.
Run the colouring across every connected component, since a disconnected graph is bipartite only when each component is.
Odd cycles are the obstacle
The deep reason a graph fails the test is an odd length cycle. Walking around a cycle, colours must alternate; an odd cycle forces two adjacent vertices to share a colour, which is the exact conflict the search detects. A graph is bipartite if and only if it contains no odd cycle.
Key idea
A graph is bipartite exactly when a two colouring search can give adjacent vertices opposite colours without conflict, which fails precisely when an odd length cycle exists.