If I have a graph with exactly two odd-length circuits, how do I prove that it is 3 colorable?
I'm thinking the base case here is that you have 2 triangular circuits put together (like a square with a diagonal edge through it). It's pretty easy to show this is 3 colorable, but I'm not sure how I could go about creating a general rule. Any thoughts?
Denote these circuits by $C_1$ and $C_2$. If the circuits $C_1$ and $C_2$ have a common vertex $v$ then remove it from $G$. The remaining graph has no odd-length circuits, so it can be colored in two colors without creating adjacent monochromatic vertices. It remains to color the vertex $v$ into a third color.
It the circuits $C_1$ and $C_2$ are vertex-disjoint. If each vertex of the circuit $C_1$ is adjacent to each vertex of the circuit $C_2$ then we can easily construct a third odd-length circuit. So there exist non-adjacent vertices $v_1\in C_1$ and $v_2\in C_2$. Remove them from $G$. The remaining graph has no odd-length circuits, so it can be colored in two colors without creating adjacent monochromatic vertices. It remains to color the vertices $v_1$ and $v_2$ into a third color.