Trace graph = [[1,2,3],[0,2],[0,1,3],[0,2]].
Start at node , color it . Queue: [0].
Pop . Neighbors , , : all uncolored. Color them . Queue: [1, 2, 3].
Pop . Neighbor : color , opposite of . Good. Neighbor : color , same as . Conflict! Return false.
Nodes and are adjacent but both need color (forced by their connection to node ). The triangle 0-1-2 is an odd cycle.
You visit each node once and each edge once: time. The color array takes space.