Question

let g be a finite connected planar graph with at least three vertices. show that g has at least one vertex of degree 5 or less
​

Answer 1

The step to show that g has at least 1 vertex of 5 degrees or more:

Step-by-step explanation:

• Let suppose that G to be any planar graph that has n vertices and m edges.
• If it is possible, let’s suppose that G does not have any vertex of degree no less than 5.  
• Hence, each vertex of G is of 6 degrees or more..  
• Then,  ∑d (v) ≥ 6n. However, ∑ d (v) =2m ≤ 6n-12 as G is a planar graph.  

• So, 6n ≤ 6n-12, this is a contradiction.  
• Hence, G must have at least one vertex of degree at most five.