Why does a two-coloring check seeded only at one start vertex wrongly report bipartite?

## The bug in one line The sweep is correct; the **driver** is not. A traversal seeded once explores exactly the connected component of its seed, and a graph can have many components. Bipartiteness must hold for all of them, so a verdict computed from one component is a verdict about one component. ## Why this is not a contrived input Conflict data is disconnected by nature. A list of vendor pairs who must not share a table describes several independent feuds, not one giant web; a list of people who must be kept apart in a rota has clusters that never touch. It is entirely normal for a graph built from such a list to have dozens of components, plus a long tail of isolated vertices — entities that appear in the roster but in no conflict at all. A single-seed check on that input inspects one feud and blesses the rest sight unseen. The failure is silent and one-directional, which is what makes it dangerous: the check never reports a false 'not bipartite', only a false 'bipartite'. It fails in the direction where nothing complains until the real-world assignment blows up. ## The fix Wrap the sweep in an outer loop: 1. Keep one color array for the whole graph, all slots unset. 2. For each vertex `s` from `0` to `n-1`: if `color[s]` is still unset, seed a new sweep at `s` with color 0. 3. Any clash found in any sweep ends the whole check with 'not bipartite'. 4. Only after the outer loop completes without a clash do you report 'bipartite'. Two details matter. First, **do not reset the color array between components** — the shared state is what stops already-finished vertices being re-explored, and clearing it turns a linear check into repeated work or an endless loop. Second, `color[s]` being unset is itself the test for 'this vertex belongs to a component nobody has touched'; you do not need a separate visited marker, because 'colored' and 'visited' are the same fact here. ## Cost Still `O(V+E)`. The outer loop scans all `V` vertices, but it only *seeds* a sweep at a vertex that is still unset, and a seeded sweep colors every vertex it reaches. So each vertex is enqueued once across the entire run, and each edge is examined from each of its endpoints once. Extra space is `O(V)` for colors plus the frontier or recursion stack. ## Independence of components Each component is colored on its own. If a graph has `c` components and is bipartite, there are `2^c` valid colorings, because each component's assignment can be flipped independently without breaking any edge — no edge crosses between components, so nothing constrains their relative orientation. A caller who needs one global 'side A / side B' split may pick any of them. This is worth stating out loud in an interview: candidates sometimes 'fix' the per-component bug and then invent a second, unnecessary rule that all components must start with the same color. Edge cases fall out of the same reasoning. A graph with no edges is bipartite (every vertex is isolated; put them all on one side, or split them arbitrarily). A graph with a single vertex is bipartite. An empty graph is vacuously bipartite. None of these should be special-cased; the loop handles them. ## The same bug wearing other clothes The defect is in the seeding, not the traversal, so switching from a queue-driven sweep to a recursive one changes nothing — a depth-first version seeded once has exactly the same hole. The same shape of bug appears in any whole-graph property computed by traversal: counting components, detecting cycles in an undirected graph, labeling reachability. Whenever a property must hold globally but a traversal only sees locally, the outer 'for every unvisited vertex' loop is the part that turns a component algorithm into a graph algorithm. ## How to catch it The cheapest test case is two disjoint blocks: a well-behaved four-vertex ring plus a five-vertex ring, with no edge between them. Any correct implementation must say 'not bipartite' regardless of which block the vertex numbering puts first. A test suite with only connected inputs will pass a broken implementation forever, which is the more general lesson: graph test data must include a disconnected case, an isolated vertex, and an empty graph, or the driver logic is untested.