Planarity

Wednesday, 24 April 2019

11:51 AM

Each  in a simple connected planar graph  is at least 3.

• To have a region of degree 1, G must have a loop
• To have a region of degree 2, G must have parallel edges

 

 

 

If  is a connected planar simple graph with  edges and  vertices, then

• 
•  (if  has no circuits of length 3)