BFS Two-Coloring for Bipartiteness

Two Colors Guided by Breadth-First Search

A graph is bipartite when its vertices can be divided into two parts so that every edge joins different parts. One way to find such a division is to assign two colors, requiring the endpoints of each edge to have opposite colors. Breadth-first search (BFS) gives a systematic order for making these assignments: when a vertex is reached, assign its uncolored neighbors the opposite color. The essential safeguard is to check a neighbor’s existing color before doing anything to it. If an already-colored neighbor has the same color as the vertex being processed, the algorithm reports failure rather than changing either assignment.

Throughout, \(G=(V,E)\) is a finite, simple, undirected graph. A proper two-coloring is a function \(c:V\to\{0,1\}\) such that \(c(u)\ne c(v)\) for every edge \(uv\in E\). Such a coloring gives a bipartition: its two parts are the vertices colored \(0\) and the vertices colored \(1\). Either part may be empty, so the definition also covers an edgeless graph.

The restart rule matters: a BFS started at one vertex reaches only its connected component. Starting a new search at each remaining uncolored vertex ensures that every component, including an isolated vertex, is handled. The parent edges form a BFS forest, with one root in each component.

Why the Search Reaches Every Vertex

Proof. Suppose instead that some vertex in the component of \(r\) remains undiscovered when the queue becomes empty. Since it is connected to \(r\), there is a path from \(r\) to that vertex. Along this path, take the first edge \(xy\), starting from \(r\), whose endpoint \(x\) was discovered and whose endpoint \(y\) was not. A discovered vertex is either waiting in the queue or has already been removed from it. In the first case, the search has not finished, because the queue is nonempty. In the second case, processing \(x\) inspected every neighbor, including \(y\), and would have discovered \(y\). Both cases contradict the assumption that the queue is empty while \(y\) is undiscovered. \(\square\)

Thus, after each restart, that BFS processes exactly the vertices of its root’s connected component. The component claim follows because BFS only follows edges, so it cannot reach a vertex outside the component, and the lemma shows that it reaches every vertex inside it.

Correctness of the Two-Coloring Test

Proof. First suppose the procedure succeeds. Every vertex is colored, since BFS processes each component and the outer scan starts a search at each vertex that remains uncolored. Consider any edge \(uv\). When the earlier of \(u\) and \(v\) was processed, the other endpoint was either uncolored and assigned the opposite color, or already colored. In the latter case, success means the two colors were different, since equal colors would have caused a conflict. Therefore \(c(u)\ne c(v)\) for every edge. The color classes give a bipartition.

Now suppose a conflict is reported on an edge \(uv\), so \(c(u)=c(v)\). The vertices \(u\) and \(v\) belong to the same BFS tree: a color is assigned only within a search started at a single root, and colors are never transferred between searches. Along every parent edge in that tree the assigned colors are opposite. Consequently, any proper two-coloring of the graph would have to alternate colors along the unique tree path from the root to each vertex. Because the algorithm assigned \(u\) and \(v\) the same color, their tree paths have the same parity of length, so any proposed proper two-coloring would put \(u\) and \(v\) in the same part. But \(uv\) is an edge, and the endpoints of an edge must be in different parts. This contradiction shows that no proper two-coloring exists. Hence a conflict proves the graph is not bipartite. Together, these arguments prove both directions. \(\square\)

The conflict is meaningful because the algorithm’s earlier assignments are constrained by the BFS tree. A same-color edge contradicts those constraints; it is not a signal to recolor one endpoint and continue. The exact report is an edge whose endpoints cannot both satisfy the required opposite-color rule under the assignments forced by the search tree.

Worked Examples

Common Mistake: Overwriting a Color

Consider the triangle in the second example. After processing vertex \(1\), both \(2\) and \(3\) have color \(1\). When processing \(2\), the edge \(23\) is a conflict because \(c(2)=c(3)=1\).

A faulty version of the algorithm might first set \(c(3)=1-c(2)=0\), then compare \(c(3)\) with \(c(2)\). It would compare \(0\) with \(1\) and miss the conflict. That is a wrong calculation: it has changed the value it needed to test. The correct order is to test whether \(3\) is uncolored. Since it is already colored, leave \(c(3)=1\) unchanged, compare it with \(c(2)=1\), and report the conflict.

Running Time and Use

With adjacency lists, each vertex is enqueued and removed from the queue at most once. Each undirected edge appears in the adjacency list of each endpoint, so its two incidences are inspected at most once each. The outer scan examines all \(n=|V|\) vertices. Thus the total running time is \(O(n+m)\), where \(m=|E|\); the color array, parent array, and queue use \(O(n)\) additional space. The algorithm gives both an answer and, on success, an explicit two-part assignment that can be checked edge by edge.

The result also explains why disconnected inputs require care. A successful search from one root establishes a coloring only for that component. The outer scan must restart from each remaining uncolored vertex; otherwise an untested component could contain a conflict. Conversely, isolated vertices need no special rejection: they receive a color when chosen as roots, and since they have no incident edges, they cannot create a conflict.