I have managed to reason that a bipartite graph can only have even length cycles with the definition of a cycle and the fact that crossing any edge $e \in V(G)$ results in a switch of partition class. But I am not sure how to show that when a connected graph $G = (V, E)$ does not have cycles of odd length, that we can construct the two partition classes $P_1, P_2 \subseteq V(G) s.t. P_1 \cup P_2 = V(G)$.
My initial ideal was to use coloring by choosing vertex $s$ to be any vertex of the maximal cycle $C$ in G and moving any subsequent vertex $t$ to either $P_1$ or $P_2$ depending on if the length from $s$ to $t$ is even or odd. But with this reasoning we cannot conclude that the two partitions would equal the original vertex set, $P_1 \cup P_2 = V(G)$, as we might not encounter every vertex in our maximal cycle. So how can I fix my proof?
Edit: It just occurred to me given the aforementioned vertex $t$, if $t$ has any neighbour $n$ s.t. $n \notin C$, we recursively iterate any such neighbour $n$ (and its neighbours $n': n' \notin C$) and move them to the appropriate set $P_1$ or $P_2$. What this would equal is more or less a proof with DFS algorithm. Can we conclude the proof with a more "mathematical" touch, so to say?
Best Answer
So one way to finish a proof is to construct sets for vertices that are even and odd distance away from a root vertex and reason whether or not it is possible that two elements from a same partition can share an edge.