I need to prove that a simple graph $G=(V,E)$ is bipartite if and only if for $vw\in E$, for all $a\in V$, the length of the shortest path from $a$ to $v$ is not equal with that between $a$ and $w$.
It's for me clear, that if two shortest paths are equal, we find $avwa$ a odd cycle so that $G$ not bipartite. But I have no idea for the other direction. Assume all those paths are not equal, and there is an odd cycle, I failed to see how to find two paths with equal length. Any hints are appreciated!
Suppose there is such edge $vw$ and such vertex $a$ that $\text{dist}(a,v)=\text{dist}(a,w)$. Consider the shortest paths from $a$ to $v$ and from $a$ to $w$. Let $u$ be their last common vertex. It exists since $v\neq w$. The length of either path from $a$ to $u$ is the same since these are the shortest paths. Hence the length of either path from $u$ to $v$ or $w$ is the same. This makes $vwu$ an odd cycle. Thus the graph $G$ is not bipartite.
Now let $G$ be non-bipartite. Let us find a vertex and an edge with its ends equidistant from the found vertex. $G$ contains an odd cycle. Fix any vertex $a$ of it. Take two “opposite” vertices in the cycle $v$ and $w$. If $\text{dist}(a,v)=\text{dist}(a,w)$ then we are done. If it’s not the case, then consider the shortest path from $a$ to $v$.
Since its length is strictly less than $\text{dist}(a,v)$ there exist such vertices $u_1$ and $u_2$ that
Vertices $u_1$ and $u_2$ break the cycle’s vertices into two groups of different parity. One of these two pieces together with the segment of the path between $u_1$ and $u_2$ form an odd cycle. Its length is strictly smaller than that of the previous cycle.
Repeat the reasoning for this smaller odd cycle. This process can’t repeat endlessly so we will eventually get that $\text{dist}(a,v)=\text{dist}(a,w)$.