Proof

Assume, \(G(V,E,\gamma)\) is an undirected graph, which is bipartite.
Then, by definition, there is a partition of vertices \(V=A\cup B,~ A\cap B=\emptyset\) with \(\gamma(e)=X\) for pairs of vertices \(X=\{x,y\}\) such that either \(x\in A, y\in B\) or \(x\in B, y\in A\) for all \(e\in E\).
Since there is a path between any two vertices in \(A\) and \(B\), and both form a partition of \(V\), the graph is connected.
It follows that every cycle \(C^k\) alternates between \(A\) and \(B\), and therefore has an even length \(k\).
It follows that there is no cycle in \(G\) with an odd length \(k\).

Assume that there is no cycle in \(G\) with an odd length \(k\) and that \(G\) is connected.
Let the distance \(d(u,v)\) between \(u,v\in V\) be the length of the shortest path between \(u\) and \(v\).
Define \(U_i:=\{v\in V~:~d(u,v)=i\}\) for \(i=0,1,2\ldots\). Note that an edge can join vertices in \(U_i\) and \(U_j\) only if \(j=i\) or \(j=i+1\) or \(j=i-1\).
Claim: There is no edge between vertices in \(U_i\).
- Otherwise, if \(y,y'\in U_i\) and \(yy'\in E\), then the shortest paths \(u-y\) and \(u-y'\) would have length \(i\) by construction.
- Let \(w\) be the last common vertex.
- Then the paths \(w-y\) and \(w-y'\) and the edge \(yy'\) form a cycle of length \(2(i-d(u,w)\) + 1, contradicting the absence of odd cycles.
By setting \(A:=U_0\cup U_2\cup U_4,\cup\ldots\) and \(B:=U_1\cup U_3\cup U_5,\cup\ldots\) we get a partition of \(G\)
Therefore \(G\) is bipartite.
∎

Thank you to the contributors under CC BY-SA 4.0!

Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000