TADM2E 5.5
From Algorithm Wiki
Graphs with max degree 2, can be bipartite (even number of edges) or tripartite (odd number of edges)
Consider a triangle (3 edges, 3 vertices): it's not bipartite even though every node has an even number of edges and the graph has an even number of edges.
For such a graph, such that the degree of every vertex is at most 2, we can use a DFS traversal, coloring the child the opposite color of the parent. When we see a Back edge, we color the currently discovered child with a color different that the parent, and also different from the ancestor discovered through that back edge.
Since there is just one traversal, it runs in O(m + n) (m edges, n vertices)
