What does it mean for a graph to be bipartite, and how does two-coloring test it?
answer
- picture two tables, not two piles
- what does each edge have to connect?
- the first vertex's color is free
- after that, every neighbour is forced
- a repeat color on an edge ends it
basics
~20 sA graph is bipartite if its vertices split into two sides with every edge crossing between them. Two-coloring tests it: color a start vertex, force each neighbour the opposite color, and fail if an edge ever joins same-colored vertices.
solid answer
~50 sBipartite means the vertices fall into two sides so that every edge has one endpoint on each side, and no edge lies inside a side. A concrete reading: two banquet tables and a list of vendor pairs who must not share a table — a valid seating is exactly a two-coloring of the conflict graph. Pick any unseated vendor, put them at table A; every vendor they conflict with is forced to table B, those vendors' partners back to A, and so on across the sweep. After the first vertex nothing is a choice, so there is no searching and no backtracking. If the sweep ever meets an edge whose two endpoints already hold the same table, no seating exists and the graph is not bipartite. The whole check costs one traversal, `O(V+E)`, plus one color per vertex.
go deeper
Be ready to define bipartite in one sentence — two sides, every edge crossing — and to walk a small conflict list by hand, assigning a start vertex and forcing its neighbours to the other side.
Explain why no backtracking is needed: within a component every color is fixed by the parity of distance from the seed, so the check is a plain traversal at O(V+E) rather than a search.
Show that you use the coloring as output, not just a boolean — the two sides are the deliverable, and a failed edge is a pointer at the exact input that makes the split impossible.
Own the framing call: decide whether a two-way split is the right model at all, or whether the domain really needs three groups or a weighted relaxation, before anyone writes the check.
## The definition, stated carefully A graph is **bipartite** when its vertex set can be partitioned into two disjoint sides — call them A and B — such that **every edge has one endpoint in A and the other in B**. Equivalently: no edge has both endpoints inside the same side. The definition says nothing about how big the sides are, how many edges there are, or whether the graph is in one piece. A single vertex, a long path, a ring of even length, a tree, and a very dense graph in which every A-vertex is joined to every B-vertex are all bipartite. Three misreadings are worth killing immediately. Bipartite does **not** mean "has two connected components" — a bipartite graph is very often connected, and a two-piece graph is usually not bipartite. It does not mean "can be drawn without crossing edges" — that is planarity, an unrelated property. And it does not mean "two colors happen to be used"; the requirement is that the coloring is *proper*, i.e. no edge joins two vertices of the same color. ## The seating model Suppose you are seating vendors at a trade banquet with exactly two tables, and you hold a list of pairs who must not sit together. Model it as a **conflict graph**: one vertex per vendor, one edge per conflicting pair. A seating that respects every conflict is precisely an assignment of one of two labels to each vertex such that no edge joins two equal labels — a **two-coloring**. So "can these vendors be seated at two tables?" and "is this conflict graph bipartite?" are the same question, word for word. ## Why the coloring is forced, and why that matters Start the sweep at any vertex that has no color yet and give it color 0. Every neighbour of it must take color 1. Every neighbour of *those* must take 0. Inside one connected piece of the graph, the color of every vertex is therefore determined by the **parity of its distance from the seed**: even distance gets the seed's color, odd distance gets the other. Only the seed's own color is a free choice, and flipping it just swaps the two sides. This is the point a junior candidate should be able to say out loud, because it explains why the algorithm is a plain traversal and not a search. There is nothing to try, nothing to undo, no order that works better than another. Graph coloring with three or more colors is a hard combinatorial problem; with two colors it collapses into a single sweep, because each vertex's color is dictated the moment one of its neighbours is colored. ## The algorithm Keep one color slot per vertex, initially unset. Traverse the graph breadth-first or depth-first from an uncolored seed. On visiting an edge from a colored vertex `u` to a vertex `v`: - if `v` is unset, give it the opposite color of `u` and continue the traversal into it; - if `v` already carries the **opposite** color, the edge is satisfied — do nothing; - if `v` already carries the **same** color as `u`, stop: the graph is not bipartite. With adjacency lists this touches each vertex once and each edge at most twice, so the cost is `O(V+E)` time and `O(V)` extra space for the colors, plus the traversal's own frontier or recursion stack. Depth-first and breadth-first give the same verdict; only the order of discovery differs, and since the colors are forced, the answer cannot depend on it. ## What a clash actually proves A same-color edge is not a sign that you colored badly. Because every color after the seed was forced, a clash means the graph itself contains a contradiction: two vertices at the *same* distance parity from the seed are joined by an edge, which closes a walk of odd length. That is the structural obstruction, and it is why re-running with a different seed, a different traversal order, or the colors swapped will always fail too. ## What the verdict buys you A yes gives you more than a boolean: the coloring itself is the split — the two tables, the two shifts, the two groups. Many later techniques need that split to exist before they can start, so a two-coloring sweep is often the first thing you do to a graph whose two-sided structure is not already obvious from the data. A no is equally useful when you can report *why*, because the failing edge points straight at the part of the input that makes the two-way split impossible.
- Does the verdict depend on which vertex you start from, or which color you give it?No. Within a connected piece, flipping the seed's color just swaps the two sides, so a bipartite graph stays bipartite and a failing one fails from any seed. The *assignment* can differ — a bipartite connected graph has exactly two valid colorings — but the yes/no answer is invariant, and so is it under choosing breadth-first or depth-first order.
- Is a tree always bipartite?Yes. A tree has no cycles at all, so it cannot contain the odd cycle that blocks two-coloring. Coloring by the parity of each node's depth from the root always works, which is why any forest, path, or star is bipartite regardless of how lopsided it looks.
- Does adding the coloring make the traversal more expensive?No. It is still `O(V+E)` with adjacency lists: each vertex is dequeued once and each edge inspected from both ends. The only extra cost is one color slot per vertex, `O(V)` space, and one comparison per edge. The check is essentially a free rider on a traversal you were running anyway.
saying these in an interview costs you the question
- Says bipartite means the graph has two connected components
- Believes a smarter coloring order could rescue a failing graph
- Backtracks over color choices instead of seeing they are forced
- Confuses bipartite with planar or with two-colorable regions
- Checks only that both colors were used somewhere