Graph theory question(about planar graphs, degrees) 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. 
 A: I'll get you started.  For a planar graph, the Euler characteristic formula (including the outer face) is $2=\#V-\#E+\#F$ where $\#V$ is the number of vertices, $\#E$ is the number of edges, and $\#F$ is the number of faces.
Assume the statement is false and that every vertex has degree at least 6.  Fix $\#E$.  Since each edge has exactly two endpoints, there are at most $\#E/3$ vertices.  Since the smallest faces are triangles and each edge is a side of two faces (this uses that the graph is planar), it follows that $\#F$ is at most $\#2E/3$.
Combining all of these, it follows that $\#V-\#E+\#F\leq\#E/3-\#E+\#2E/3=0$.  Therefore, there must be at least one vertex with degree less than 6.
If you continue the analysis, let $m$ be the number of vertices with degree at least 2 but not more than 5.  In this case, the analysis above is unchanged, but the number of vertices is at most $\left(\frac{2\#E-2m}{6}\right)+m=\frac{\#E}{3}+\frac{2m}{3}$.  Plugging this into the Euler characteristic formula, you find that $m$ is at least 3.
A: 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........!

