0
$\begingroup$

I'm asked to prove using induction on the vertices of a graph that if it has no cycles of odd length it is bipartite. I'm aware of the usual contradiction proof, but I'm trying to accomplish it by induction.

Here's what I've done until now.

Base case: When $|V(G)| = 2$ it is easy to see there's no cycles of odd length and is bipartite.

Hypothesis: A graph $G$ without cycles of odd length and with $|V(G)| < L$ is bipartite.

Inductive step: Let G be a graph with $|V(G)| = L$, if G has no cycle with odd length, we can remove any vertex $v$ from $V(G)$ and, using our hypothesis, $G-v$ is bipartite.

And I'm stuck here. What I've done is basically reduce my graph so it fits the hypothesis, but that's not enough to prove that it is valid for $|V(G)| = L$. I tried thinking about a way to show that since $G-v$ is a subgraph of $G$ and $G-v$ is bipartite then $G$ also is, but that is not true. I have no idea how to continue my proof. Appreciate any kind of help.

$\endgroup$
1
$\begingroup$

Give your graph $G-v$ a (black/white) vertex colouring corresponding to its bipartition. Consider the neighbours of $v$ in $G$, say $w_1,\ldots,w_k$. If they all have the same colour, you are fine. Suppose not, for instance, $w_1$ is black and $w_2$ is white. Then $w_1$ and $w_2$ are in different components of $G-v$ for otherwise there's a path in $G-v$ from $w_1$ to $w_2$ and extending this to $v$ and then back to $w_1$ gives an odd length cycle in $G$. As $w_1$ and $w_2$ are in different components of $G-v$ if one reverses the colours of the vertices in one component, $w_1$ and $w_2$ both gain the same colour. Repeat, until all the $w_i$ have the same colour...

$\endgroup$
  • $\begingroup$ Sorry, I don't see how this proves that G is bipartite if it doesn't have an odd length cycle using induction. $\endgroup$ – Alonso Ali Sep 8 '17 at 5:23
  • 1
    $\begingroup$ It should be easy to see that $G$ is bipartite if and only if it is 2-colorable. Now, observe two properties that hold after adding $v$ back to $G-v$: 1) No two neighbors of $v$ belong to different color classes in the same component. (This is the only case where the number of odd cycles could increase). 2) From 1 it follows that if $v$ is adjacent to vertices in different components, then you may swap colors in components (if necessary) to obtain a two coloring of $G$. Thus obtaining a certificate that $G$ is bipartite. $\endgroup$ – fidbc Sep 8 '17 at 14:48

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.