Suppose that $G$ is a graph with $n$ vertices and $5n−10$ edges. Prove that $G$ has a vertex of degree at most $9$.

I am stuck on how to approach this.

I see that there are two cases:

  1. $n \le 10$, in this case no vertex can have a degree higher than $9$.
  2. $n > 10$.

I cannot figure out how to prove the problem for the second case.

If it matters, we are working on planar graphs in class right now.


Hint: The sum of the degrees is twice the number of edges, so $\sum \text{deg}(v) = 2(5n - 10) = 10n - 20$.

What happens if all of the vertices have degrees 10 or more?

| cite | improve this answer | |

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.