Proving 2-Coloring of Planar Graphs with Even Region Boundaries

  • Thread starter SNOOTCHIEBOOCHEE
  • Start date
  • Tags
    even Graphs
In summary, the conversation discusses proving that a planar graph with an even number of bounding edges in each region can be 2-colored. The suggested approach is to use induction on the number of regions. The first step is to show it is true for a graph with only two regions, and then assume it is true for a graph with n regions and use that to prove it for a graph with n+1 regions by deleting one of the boundaries.
  • #1
SNOOTCHIEBOOCHEE
145
0

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.
 
Physics news on Phys.org
  • #2
any takers?
 
  • #3
Sorry for the bump, but i still need help on this.
 
  • #4
SNOOTCHIEBOOCHEE said:
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! :smile:

It's obviously true for a graph with only one face … so how about a proof by induction? :smile:
 
  • #5
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.
 
  • #6
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:
 

FAQ: Proving 2-Coloring of Planar Graphs with Even Region Boundaries

What is a planar graph?

A planar graph is a type of graph that can be drawn on a flat surface without any of its edges crossing. In other words, it can be represented on a two-dimensional plane without any intersections.

What does it mean to 2-color a planar graph?

2-coloring a planar graph means assigning one of two colors (typically red and blue) to each vertex in the graph, such that no two adjacent vertices have the same color. This creates a coloring pattern where adjacent vertices have different colors, and the entire graph can be colored using only two colors.

Why is it important to prove 2-coloring of planar graphs with even region boundaries?

Proving 2-coloring of planar graphs with even region boundaries is important because it helps in understanding the properties of planar graphs and their colorings. It also has applications in various fields such as computer science, graph theory, and map coloring problems.

How is the 2-coloring of planar graphs with even region boundaries proven?

The 2-coloring of planar graphs with even region boundaries can be proven using the Four-Color Theorem, which states that any planar graph can be colored using only four colors. This theorem can be used to prove the 2-coloring of planar graphs with even region boundaries by reducing the graph to a simpler form and applying the Four-Color Theorem.

Are there any real-life applications of the 2-coloring of planar graphs with even region boundaries?

Yes, there are several real-life applications of the 2-coloring of planar graphs with even region boundaries. One of the most well-known applications is in map coloring, where the regions on a map can be represented as vertices in a planar graph and the colors can represent different countries or states. This problem can be solved by 2-coloring the planar graph, ensuring that no two adjacent regions share the same color.

Similar threads

Prove the decomposition of a graph w/ even edges produce a 2-path set
Replies
1
Views
1K
Prove that there exists a graph with these points such that....
Replies
2
Views
1K
B 4-colours theorem can be proved visually
Replies
21
Views
1K
Euler circuit in a directed multigraph
Replies
2
Views
5K
Proving Cut Vertices in Simple Graphs
Replies
2
Views
1K
Proving a (known isomorphic) graph is isomorphic
Replies
6
Views
2K
Strong Induction, Tangled Graph
Replies
3
Views
3K
Proving "3f ≤ 2e" for Planar Graphs
Replies
1
Views
2K
Parametrization of a Parallelogram: Mapping Rectangles onto Planar Regions
Replies
1
Views
959
Almost All Graphs are Non-Planar
Replies
1
Views
2K

Hot Threads

Recent Insights

Back
Top