Does a triangle-free graph have to be bipartite, and what is the exact test?
answer
- triangle-free is only one obstruction
- walk a cycle alternating sides
- what happens when the cycle closes?
- try a ring of five vertices
- the parity of cycle length decides
basics
~20 sNo. Triangle-free is necessary but not sufficient: a ring of five vertices holds no triangle yet cannot be two-colored. The exact characterization is that a graph is bipartite if and only if it contains no cycle of odd length.
solid answer
~40 sTriangle-free is only half the story. A triangle is an odd cycle, so every bipartite graph is triangle-free — but the converse fails at the very next odd length. Take five vendors in a conflict ring, each clashing only with its two ring neighbours: color them alternately A, B, A, B, A around the ring and the final edge joins two A's. There is no triangle anywhere, and still two tables are impossible. The exact statement is: a graph is bipartite **iff** it has no odd-length cycle. Even cycles are harmless because the alternation closes cleanly, and acyclic graphs are trivially fine. That is also why a two-coloring sweep is a complete test — a color clash is exactly an odd cycle being closed, not a symptom of one specific cycle length.
go deeper
Know that a triangle rules out a two-way split, and be able to try a five-vertex ring by hand and see the last edge clash. That single example is what the question is testing.
State the iff cleanly — bipartite exactly when there is no odd cycle — and sketch both directions: alternation forces even cycles, and distance parity colors a graph with no odd cycle.
Turn the failure into evidence: keep parent pointers so a clash yields the actual odd cycle, and hand that to whoever owns the input rather than reporting a bare 'impossible'.
Decide what the team does with an impossible verdict — a third group, dropping a conflict, or a soft-constraint formulation — and be clear that removing one edge of one odd cycle need not fix the rest.
## The claim under test "No triangles, so it splits into two groups" is one of the most common wrong answers about bipartiteness, and it is wrong in an instructive direction: the implication holds one way only. - **Bipartite implies triangle-free.** A triangle is three mutually adjacent vertices. With only two sides available, two of the three must land on the same side, and the edge between them lies inside a side. So a triangle can never appear in a bipartite graph. - **Triangle-free does not imply bipartite.** The obstruction is not "length three"; it is **odd length**. ## The smallest counterexample Five vendors, each in conflict with exactly two others, arranged so the conflicts form one ring: v1-v2, v2-v3, v3-v4, v4-v5, v5-v1. No three of them mutually conflict, so there is no triangle. Now try two tables. Put v1 at A. Then v2 is forced to B, v3 to A, v4 to B, v5 to A. The last conflict, v5-v1, joins two vendors both at table A. Every step was forced, so nothing else could have been done: five vendors in a ring cannot be split across two tables. The same failure occurs on a seven-ring, a nine-ring, and every odd ring. Meanwhile a four-ring, a six-ring, or any even ring alternates perfectly and closes on the correct side. ## The exact characterization > A graph is bipartite **if and only if** it contains no cycle of odd length. Both directions are worth being able to sketch. **Bipartite implies no odd cycle.** Walk around any cycle in a bipartite graph. Every edge crosses from one side to the other, so the side alternates at every step. To return to the starting vertex you must be back on the starting side, which takes an even number of alternations. Hence every cycle has even length. **No odd cycle implies bipartite.** Work one connected piece at a time. Pick any vertex as the seed and color each vertex by the parity of its shortest distance from the seed: even distance gets side A, odd distance gets side B. If some edge joined two vertices of the same parity, then combining the two shortest paths from the seed with that edge produces a closed walk of odd length, and a closed walk of odd length always contains an odd cycle. Since no odd cycle exists, no such edge exists, and the parity coloring is a valid split. That second argument is exactly what a two-coloring sweep computes, which is why the sweep is not a heuristic: it is a decision procedure that is complete. ## Where the coloring breaks, precisely During a sweep, when the algorithm reports a clash on edge `(u, v)` with both endpoints the same color, it is holding an odd cycle in its hands. The traversal recorded a parent for each colored vertex; walk from `u` and from `v` back through parents to their nearest common ancestor. The two upward paths have the same parity of length — that is what "same color" means — so those two paths plus the edge `(u, v)` form a cycle of odd total length. Keeping parent pointers therefore upgrades a boolean answer into a **certificate** you can print: here are the specific vendors whose mutual conflicts make two tables impossible. ## Things that do not follow A few adjacent claims are wrong and get offered under pressure: - **"Dense graphs cannot be bipartite."** False. A complete bipartite graph joins every vertex of one side to every vertex of the other; with sides of size `a` and `b` it has `a*b` edges, up to about `n^2/4` for `n` vertices. Bipartite graphs can be very dense. - **"Bipartite means acyclic."** False. Any even cycle is bipartite and full of cycles. Acyclic is a strictly stronger, unnecessary condition. - **"Even cycles also break two-coloring."** False, and it is the mirror error of the triangle claim. Alternation around an even cycle closes correctly. - **"Checking for triangles is a cheap approximation."** It is not even a useful screen: enumerating triangles is more expensive than the linear two-coloring sweep, and it can only ever produce false 'bipartite' verdicts on graphs whose shortest odd cycle is longer than three. ## Why the framing matters at the whiteboard When a conflict-grouping problem is posed, the useful reflex is not "look for triangles" but "run the forced coloring and see whether it closes". The sweep costs one linear pass, answers the question exactly, and — with parent pointers — hands back either the two groups or the specific odd cycle that rules them out. Any argument that stops at triangles is answering a strictly weaker question.
- Where exactly does the alternation break on an odd cycle?Colors alternate at every edge, so a vertex at even distance along the cycle carries the start's color. Closing a cycle of odd length brings you back to the start from a vertex of the same parity, and that final edge joins two equal colors. The alternation is fine everywhere except the closing edge, which is why length parity is the whole story.
- How do you produce the odd cycle as evidence when the check fails?Record a parent for each vertex as you color it. When edge `(u, v)` clashes, walk both endpoints up through parents to their nearest common ancestor. The two upward paths have equal parity, so together with the clashing edge they form a cycle of odd length — a printable certificate naming the exact vertices that make the split impossible.
- Can a bipartite graph be dense?Yes. A complete bipartite graph joins every vertex of one side to every vertex of the other; with sides of size `a` and `b` that is `a*b` edges, peaking near `n^2/4` for `n` vertices. Density and bipartiteness are independent, so 'too many edges to be bipartite' is not an argument.
saying these in an interview costs you the question
- Claims no triangles is enough to guarantee bipartiteness
- Thinks only cycles of length three block two-coloring
- Says even cycles also break the alternation
- Believes dense graphs cannot be bipartite
- Confuses bipartite with acyclic
- Proposes triangle enumeration as a cheap pre-check