Proving 2-Coloring of Planar Graphs with Even Region Boundaries

[SNOOTCHIEBOOCHEE]

Homework Statement

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

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 don't know if that's true or how to prove it.

Any help is appreciated.

 

[SNOOTCHIEBOOCHEE]

any takers?

 

[SNOOTCHIEBOOCHEE]

Sorry for the bump, but i still need help on this.

 

[tiny-tim]

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

Hi SNOOTCHIEBOOCHEE!

It's obviously true for a graph with only one face … so how about a proof by induction?

 

[SNOOTCHIEBOOCHEE]

so I am 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. I am 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 don't know how to phrase this.

 

[tiny-tim]

Hi SNOOTCHIEBOOCHEE!

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.