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?

  • $\begingroup$ Is there a particular reason why you want to prove that with induction on the number of vertices? Since there is an "almost trivial" argument for this statement. However also induction on edges works if I'm not mistaken and is in my opinion more "natural" then induction on vertices since "being bipartite" is something concerning edge-colorings. $\endgroup$ – M.U. Sep 22 '15 at 21:54
  • $\begingroup$ It's part of an assignment, actually $\endgroup$ – gcolucci Sep 22 '15 at 22:24
  • 1
    $\begingroup$ And you "must" prove it with induction in number of vertices? $\endgroup$ – M.U. Sep 23 '15 at 5:24
  • $\begingroup$ Yes, that's the method I'm required to use... $\endgroup$ – gcolucci Sep 24 '15 at 1:33

Your Answer

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

Browse other questions tagged or ask your own question.