If graph is not bipartite then every pair of vertices can be connected by a path of even length. 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.
 A: 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
                 / \
                *---*

A: 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).
