2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you know about the Euler characteristic? $\endgroup$ – Michael Burr Mar 1 '15 at 14:12
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.