TITLE: Graph theory question(about planar graphs, degrees)
QUESTION [2 upvotes]: Prove, that every planar graph, which has no loops or multiple edges, and has more than 3 vertices(it can be 3 too), has at least 3 vertices, which have 5 or less degree.
I kinda can't start this, I know that the minimal degree of a planar graph must be lower than 6, but I can't really prove this statement.

REPLY [0 votes]: Let G(V,E) be a graph with no self loops and parallel edges.Let m be the number of vertices and n be the number of edges.Given m>=3.So,
                               n=(m(m-1))/2
Given m>=3.So, n>=(3(3-1))/2
            => n>=(3*2)/2
            => n>=3
From theorem sum of total degree of a graph = 2*n
           => sum of total degree of a graph >=2*3=6 -------------------(1)
Lets assume the given statement to be false,that is, the graph has a at least 3 vertices with degree >=6 .So the sum of total degree >=6+6+6
                        => sum of total degree >=18   -------------------(2)
For the statements (1) and (2) to be same ,the degree of a vertex in a graph must be >=2 and not 6. since from (1) n will never be equal to 9
         then only the sum of total degree >=2+2+2 

=6
  Hence the proof........!
{"set_name": "stack_exchange", "score": 2, "question_id": 1170329}