1

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!

blomp
  • 494
toki
  • 95
  • Consider an odd cycle in $G$, of length $2n+1$, and label its nodes, as traversed, $0, 1, 2, \ldots, 2n$. Then, consider the edge $(0,1)$, and the vertex $n$. Then along the cycle, both $0$ and $1$ are distance $n$ from this vertex. By assumption the minimum distances can't equal. Using this you can construct a smaller odd cycle (why?). Repeating this you arrive at a contradiction (why?). – blomp Feb 24 '24 at 15:37

1 Answers1

1

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

  • they belong both to the path and the cycle,
  • all the vertices on the path between $u_1$ and $u_2$ don’t belong to the cycle,
  • there is more that one edge on the cycle between $u_1$ and $u_2$.

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)$.

Aig
  • 4,178
  • I have a question. Why all vertices between $u_1$ and $u_2$ are not in cycle? – toki Feb 25 '24 at 12:33
  • The path is shorter than the cycle. There must be some “cut” down the road, the alternative path. We can deviate from the cycle, and take a shorter route. $u_1$ is the start of the cut, $u_2$ is the end of it. – Aig Feb 25 '24 at 12:45
  • If the cut returns to the cycle multiple times, we just take the segment of it, where it doesn’t. – Aig Feb 25 '24 at 12:46