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.
Best Answer
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$.