Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory

  1. Jul 5, 2008 #1
    1. The problem statement, all variables and given/known data

    Show that if every region in a planar graph has an even number of bounding edges, then the vertices can be 2-colored.


    3. The attempt at a solution

    So i think it would suffice to show that if that all the regions have an even number of boundary edges, then, a complete circuit with even length must exist.

    But i dont know if thats true or how to prove it.

    Any help is appreciated.
     
  2. jcsd
  3. Jul 5, 2008 #2
    any takers?
     
  4. Jul 6, 2008 #3
    Sorry for the bump, but i still need help on this.
     
  5. Jul 6, 2008 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi SNOOTCHIEBOOCHEE! :smile:

    It's obviously true for a graph with only one face … so how about a proof by induction? :smile:
     
  6. Jul 7, 2008 #5
    so im guessing we do an induction on the number of regions.

    This is obvious when there is only 2 regions.

    Assume this is true for a graph with n regions, each having an even number of bounding edges.

    then for n+1 regions...

    i get stuck here. im guessing we can some how show that something with n+1 even bounded regions some how is equal/equivalant/isomorphic (whatever the correct terminology is) to another graph with n regions. but i dont know how to phrase this.
     
  7. Jul 7, 2008 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi SNOOTCHIEBOOCHEE! :smile:

    For n+1 regions, just delete one of the boundaries to give only n regions. Colour the vertices of that, then colour the extra vertices you just removed … all you have to prove is that those extra colours still fit. :smile:
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook