3
$\begingroup$

Let $G = (V, E)$ be a graph with nine vertices, such that each vertex has degree $5$ or $6$. Show that $G$ has at least five vertices of degree $6$, or at least six vertices of degree $5$.

My friend and I have been working on this question for the past two days and we have nothing. Any pointers or help?

$\endgroup$
  • 5
    $\begingroup$ If neither of those things are true, $G$ has exactly $5$ vertices of degree $5$ and exactly $4$ vertices of degree $6$. Can you see why this is impossible? $\endgroup$ – Micah May 11 '13 at 19:39
  • $\begingroup$ Oh my goodness, thank you. Both to Micah and Hagen. $\endgroup$ – Evan May 11 '13 at 19:59
  • 1
    $\begingroup$ @AbdulMalekAltawekji: Do you mean you don't understand why my hint is true, or you don't understand why it helps do the problem? $\endgroup$ – Micah Dec 12 '17 at 18:59
  • 1
    $\begingroup$ If $G$ does not have at least 5 vertices of degree 6, it has at most 4 vertices of degree 6. If $G$ does not have at least six vertices of degree 5, it has at most 5 vertices of degree 5. If it doesn't have exactly the maximum number in both cases, it doesn't have enough vertices (you know it has nine). $\endgroup$ – Micah Dec 13 '17 at 5:20
  • 1
    $\begingroup$ For how it helps, look at Hagen's hint. $\endgroup$ – Micah Dec 13 '17 at 5:20
3
$\begingroup$

Hint: The sum of all vertex degrees is twice the number of edges.

$\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.