Here is the core theorem: a graph is bipartite if and only if it has no odd-length cycles. Why?
Try to -color a triangle (cycle of length ). Color node A red. Its neighbor B must be blue. B's neighbor C must be red.
But C connects back to A, and both are red. Contradiction. Any odd cycle causes this problem. The colors "wrap around" incorrectly. Even cycles work fine: colors alternate perfectly and match up when you complete the loop.