Let \(\GVE\) be a \(2\)-colorable graph whose coloring function partitions \(V\) as \(A\cup B\text{.}\) Since there are no edges between vertices on the same side of the partition, any cycle in \(\bfG\) must alternate vertices between \(A\) and \(B\text{.}\) In order to complete the cycle, therefore, the number of vertices in the cycle from \(A\) must be the same as the number from \(B\text{,}\) implying that the cycle has even length.

Now suppose that \(\bfG\) does not contain an odd cycle. Note that we may assume that \(\bfG\) is connected, as each component may be colored individually. The *distance* \(d(u,v)\) between vertices \(u,v\in V\) is the length of a shortest path from \(u\) to \(v\text{,}\) and of course \(d(u,u) = 0\text{.}\) Fix a vertex \(v_0\in V\) and define
\begin{equation*}
A = \{v\in V\colon d(u_0,v)\text{ is even}\}\qquad\text{and}\qquad B = \{v\in V\colon d(v_0,v)\text{ is odd}\}.
\end{equation*}
We claim that coloring the vertices of \(A\) with color \(1\) and the vertices of \(B\) with color \(2\) is a proper coloring. suppose not. Then without loss of generality, there are vertices \(x,y\in A\) such that \(xy\in E\text{.}\) Since \(x,y\in A\text{,}\) \(d(v_0,x)\) and \(d(v_0,y)\) are both even. Let
\begin{equation*}
v_0,x_1,x_2,\dots,x_n=x
\end{equation*}
and
\begin{equation*}
v_0,y_1,y_2,\dots,y_m= y
\end{equation*}
be shortest paths from \(v_0\) to \(x\) and \(y\text{,}\) respectively. If \(x_1\neq y_j\) for all \(1\leq i\leq n\) and \(1\leq j\leq m\text{,}\) then since \(m\) and \(n\) are both even,
\begin{equation*}
v_0,x_1,x_2,\dots,x_n=x,y=y_m,y_{m-1},\dots,y_2,y_1,v_0
\end{equation*}
is an odd cycle in \(\bfG\text{,}\) which is a contradiction. Thus, there must be \(i,j\) such that \(x_i=y_j\text{,}\) and we may take \(i,j\) as large as possible. (That is, after \(x_i=y_j\text{,}\) the two paths do not intersect again.) Thus,
\begin{equation*}
x_i,x_{i+1},\dots,x_n = x,y=y_m,y_{m-1},\dots,y_j=x_i
\end{equation*}
is a cycle in \(\bfG\text{.}\) How many vertices are there in this cycle? A quick count shows that it has
\begin{equation*}
n-(i-1)+m-(j-1)-1=n+m-(i+j)+1
\end{equation*}
vertices. We know that \(n\) and \(m\) are even, and notice that \(i\) and \(j\) are either both even or both odd, since \(x_i = y_j\) and the odd-subscripted vertices of our path belong to \(B\) while those with even subscripts belong to \(A\text{.}\) Thus, \(i+j\) is even, so \(n+m-(i+j)+1\) is odd, giving a contradiction.