Bipartite graphs
A graph is bipartite if its vertices can be split into two groups so that every edge connects a vertex in one group to a vertex in the other. No edge stays inside a group. Bipartite structure shows up in matching problems, scheduling, and conflict modeling.
Two coloring
The test is a graph traversal that tries to two color the vertices. Imagine red and blue.
- Start any vertex with one color, say red.
- Every neighbor must get the opposite color, blue.
- Continue across the graph, alternating colors along every edge.
If you ever find an edge whose two endpoints already share the same color, the coloring is impossible and the graph is not bipartite.
Why a conflict means failure
A same color edge means two vertices that must be in different groups are forced into the same group. The deeper reason is that a graph is bipartite exactly when it contains no cycle of odd length. The traversal detects an odd cycle as a coloring clash.
You can run this with BFS or DFS across every component, since a disconnected graph needs each piece checked.
Key idea
A graph is bipartite if and only if a two coloring succeeds, which fails precisely when the graph holds an odd length cycle.