I'm trying to prove a part of König's Theorem using induction on the number of vertices. Let G be a graph with no odd cycles, |V(G)| = n. Supposing that every graph with no odd cycles with less than n vertices is bipartite, it's easy to see that G-v is bipartite, with bipartitions, let's say, X and Y. Also, when I re-include v in the graph, if all neighbours of v are in X (or Y), then v belongs to the opposite partition and G remains bipartite.
But and if v has neighbours in both bipartitions? How do I show that a simple "depth-first coloring" produces a (X',Y')-bipartition?