Prove using induction that if a graph has no odd cycles it is bipartite

[Superyoshiom]

We learned in class how to do this problem the more traditional way, but we are required to reprove this using induction, which I'm not too sure how to do.

My Attempt: For the base case I had three vertices connected by three edges, with the last one looping back to the first to create a cycle of edge length three. I said this was bipartite since you could color the two vertices that weren't adjacent red and the middle one blue and no two vertices of the same color would be adjacent to each other. However, I'm not too sure how to proceed from there for the inductive step.

 

[stevendaryl]

I think the key to this is to assume that you have a bipartite graph, and add one more vertex.

So let's assume that the original graph is split into blue vertices and red vertices. Being bipartite means that every edge leaving a blue vertex connects to a red vertex, and vice-versa.

Now, let's introduce another vertex and some more edges connecting it to the original graph. If it connects to only red vertices, then it can be a blue vertex, and we have a new bipartite graph with one more vertex. If it connects only to blue vertices, then it can be a red vertex, and we still have a bipartite graph. Notice that in both cases, you don't introduce any new cycles.

Now, suppose that the new vertex connects to both a red vertex and a blue vertex. What you need to argue is that connecting to both red and blue vertices must produce an odd cycle (if those vertices are themselves connected by edges---you might have to reason separately about disconnected vertices).