0
$\begingroup$

Suppose $G$ is an undirected graph which is non-bipartite and is connected.

Is there a way to show that given two vertices $a$ and $b$, there exists a path of even length between the two ?

I tried to use the fact that there exist odd length cycles in a non-bipartite graph but couldn't use it to prove above statement .

$\endgroup$
0
$\begingroup$

Assuming a path allows crossing the same edges and vertices:

We are given vertices $a$ and $b$. We know that the graph contains a cycle of odd length. Let $c$ be a vertex on that cycle. Further, since the graph is connected, there exist paths $a\rightarrow c$ and $c\rightarrow b$. If the total length of the path $a\rightarrow c \rightarrow b$ is even, we are done. If not then consider the path $a\rightarrow c \rightarrow (\text{odd cycle back to $c$}) \rightarrow b$.

$\endgroup$
  • $\begingroup$ Yes, in my case the path allows repeated vertices so this seems to work. $\endgroup$ – illogical Nov 17 '15 at 20:13
  • $\begingroup$ Then your path is a walk. $\endgroup$ – Moritz Nov 18 '15 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.