0
$\begingroup$

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

$\endgroup$

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .