I have a problem with this proof: https://stanford.edu/~rezab/classes/cme305/W15/Notes/problem_session_sols.pdf
Let G be a graph with no odd cycles. We will consider the case that G
is connected; this is sufficient since if we can show that each
connected component of a graph is bipartite, then it follows that the
graph as a whole is bipartite. Let d(u, v) denote the length of the
shortest path between two vertices in G. Pick an arbitary vertex u ∈ V
and define A = {u} ∪ {w | d(u, w) is even}. Define B = V \ A. We claim
that the partition V = A ∪ B demonstrates that G is bipartite. Assume
for contradiction that there exists an edge {w, v} ∈ E with w, v ∈ A
(or B). Then by construction d(u, w) and d(u, v) are both even (or
odd). Let Puw and Pvu be the shortest paths connecting u to w, and v
to u respectively. Then the cycle given by Puw, {w, v}, Pv,u has
length 1 + d(u, w) + d(u, v), which is odd, a contradiction. Therefore
no such edge {w, v} may exist and G is bipartite.
How do we know that $P_{u,w}$ and $P_{v,u}$ are disjoint? And that $v$ does not occur in $P_{u,w}$ and that $w$ does not occur in $P_{v,u}$?
Best Answer
This is not a mistake, it's just a conflict of terminology.
The terminology I consider more modern uses closed walk for the general concept of a sequence of vertices and edges in the graph that represents going from vertex to adjacent vertex for a while and eventually returning where you started. A cycle is a closed walk with no repetition of vertices or edges aside from the first and last vertex being the same. From this point of view, the proof above looks odd.
It is also not too uncommon to replace the terms "closed walk" and "cycle" by "cycle" and "simple cycle", respectively. This seems to be the terminology used by the author of these solutions, since later on the solutions mention an "Eulerian cycle". So there is no mistake in the proof; it just proves a different statement (for which we do not need to check any of these disjointness conditions).
Going back to the first terminology, we have here a correct proof that a graph is bipartite if and only if it has no closed walks of odd length. It is also true that a graph is bipartite if and only if it has no cycles of odd length, but to see this requires an additional step: showing that if a graph has an odd closed walk, then it has an odd cycle. (The converse is immediate.)
The quickest way to see that is to let $W$ be the shortest odd closed walk. If $W$ is not a cycle, then a vertex in the middle of $W$ is visited multiple times. This lets us break up $W$ into two shorter walks, $W_1$ and $W_2$, with the length of $W$ equal to the sum of the lengths of $W_1$ and $W_2$; then one of $W_1$ and $W_2$ will be a shorter odd closed walk, contradicting our initial assumption. So $W$ is actually an odd cycle.