Let G be a planar graph with at least 3 verticies. Prove that G contains at least 3 verticies whose degree is $\leq 5$.

What i have tried to do:

Lets suposse that there exist a planar graph with at least 3 verticies that has only at most 2 verticies whose degree is $\leq 5$. Therafore the sum of verticies degress in that graph :

$2E \geq 6(n-2) \implies E \geq 3n - 6$

from the Newton i know that

$E \leq 3n - 6$

So $E=3n-6$ and there is no contradiction so prove fails

any ideas how to prove it


I found it out, forgot that i can use Euler only when it is connected

Let G be the graph with the smallest verticies number but greater or equal 3 who has at most 2 verticies with degree lesser or equal 5. G must be connected graph cuz if wasn't i could take connected subgraph out of him who would still be counterexample so G wouldn't be smallest).

Sum of verticies degrees in graph must satisfy this inequality:

2E >= 6(n-2) + 2 || 6(n-2) becouse only 2 verticies are allowed to be have lesser degree then 6 and + 2 becouse G is connected so there are no verticies with degree 0 (so reamaning 2 verticies have at least degree equal 1.

After some math:

E>= 3n - 5 from equler E <= 3n - 6

Got contradiction. So G must have more then 2 verticies with degree less or equal 5


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.