Graph theory question(about planar graphs, degrees)

Question

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.

Answer 1

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.

Answer 2

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........!