# Homework Help: Graph Theory

1. Jul 5, 2008

### SNOOTCHIEBOOCHEE

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. Jul 5, 2008

any takers?

3. Jul 6, 2008

### SNOOTCHIEBOOCHEE

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

4. Jul 6, 2008

### tiny-tim

Hi SNOOTCHIEBOOCHEE!

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

5. Jul 7, 2008

### SNOOTCHIEBOOCHEE

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.

6. Jul 7, 2008

### 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.