Bipartiteness check

Bipartiteness check

Introduction

Depth First Search, or DFS, is not only used for visiting vertices. Very often, we use DFS to carry information through a graph. One important example is bipartite checking.

A graph is bipartite if we can split all vertices into two groups so that every edge goes between different groups. No edge is allowed to connect two vertices from the same group. Another way to imagine it is coloring every vertex with one of two colors, for example color $1$ and color $2$, so that every edge connects vertices of different colors.

This idea appears in many competitive programming problems: checking if people can be separated into two teams, detecting odd cycles, solving graph constraints, and building the first step before matching algorithms.

Problem or motivation

We are given an undirected graph with $n$ vertices and $m$ edges. We need to determine whether it is possible to color every vertex with one of two colors such that for every edge $(u, v)$, vertices and have different colors.