1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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


    User Avatar
    Science Advisor
    Homework Helper


    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


    User Avatar
    Science Advisor
    Homework Helper


    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