Let $G = (V, E)$ be a $3$-critical graph. Show that $G$ is a circle with odd length.
One could start the following way:
Since $G$ is $3$-critical, we can assume that $G/v$ has chromatic number $2$ for every vertex $v \in V$. This is equivalent to $G/v$ being a bipartite graph, hence, every circle of $G/v$ has even length.
This is where I wasn't able to go further. I took a look in some proofs, but oddly enough, the proofs just use the fact that I mentioned before and conclude that every $3$-critical graph must be a circle with odd length because of it. I don't see why though.
Just because we know that every circle in $G/v$ has even length, this doesn't even mean that $G/v$ does indeed have such circles, not even talking about $G/v$ being "nearly" a circle itself. Can anybody explain to me what I am missing here?
Best Answer
You are close with your idea, but missing the point slightly. Remember that color critical graphs are graphs whereby removing any vertex, the chromatic number decreases. Another way to say this is that any proper induced subgraph has a smaller chromatic number than the original graph. What you call a circle I will hereafter call a cycle.
With this in mind, let $G$ be a $3$-critical graph. Since $G$ is not 2-colorable, $G$ contains an odd cycle. Let $C$ be the smallest odd cycle of $G$. Then the graph of $G$ induced by $V(C)$ is exactly $C$ (check this). If $G \neq C$, then $C$ is a proper induced subgraph with chromatic number $3$, the same as $G$. Thus $G = C$, and we conclude that every $3$-critical graph is an odd cycle (the reverse direction is left to you).