If graph is not bipartite then every pair of vertices can be connected by a path of even length.

Question

Can someone help me understand why if graph is not bipartite then we can connect every pair of vertices by a path of even length?

I can prove that if the graph is bipartite then we can assume that any two vertices are in a cycle together. For if it has a cut-path, delete it and continue by induction on the components. So any 2 verties must be in an even cycle, so any two vertices will be connected by a path of even legth.

However, we can't just say that if graph is not bipartite, then any 2 vertices can be in a path of odd length (while it is true if they are in an odd cycle). There should be some extra step.

Can someone please help? Thank you very much.

Answer 1

We assume that the graph is connected. Then every two vertices may be joined by a path.

Now, recall the result: a graph is bipartite if and only if all its cycles have even length. So, if the graph is not bipartite, there exists a cycle of odd length from a vertex $r$ to itself.

Now, consider two vertices $p$, $q$. Join $p$ with $r$ by a path, and $r$ with $q$ by a path. Concatenate these to get a path from $p$ to $q$. Now, it this path has even length, we are done, if not, add in the middle the cycle of odd length from $r$ to itself. We thus get a path from $p$ to $q$ of even length. (Note that we can also get a path of odd length from $p$ to $q$)

Observation: About the definition of a path: a sequence of vertices $(p_0, p_1, \ldots, p_n)$ such that $(p_{i-1},p_{i})$ is an edge for all $1\le i \le n$. The $p_i$ may not be distinct. The length of the path is $n$.

(This may have some other names, it is probably what it should mean in the statement of the problem).

Answer 2

This is false. Let $G$ be the disjoint union of $K_2$ and $K_3$, like this:

$$\mid\quad\triangle$$

then $G$ is not bipartite, since it contains an odd cycle, but there is no path of even length between the two vertices of $K_2$.

A slight modification shows that requiring $G$ to be connected does not help, as the graph below is also a counterexample: there is no path of even length between $v$ and $w$.

                  v
                  |
                  w
                 / \
                *---*