Zeigen Sie, dass der Graph G mindestens eine Ecke mit Grad 4 besitzt.

Question

Aufgabe:

Text erkannt:

Sei \( G \) ein Graph mit 7 Ecken, und alle Ecken haben entweder Grad 4 oder 5. Zeigen Sie, dass der Graph \( G \) mindestens eine Ecke mit Grad 4 besitzt.

Problem/Ansatz:

Ich finde keinen Ansatz!

Answer 1

Nimm an, dass alle Ecken den Grad 5 haben und
zeige , dass dies dem Handschlaglemma
(https://de.wikipedia.org/wiki/Handschlaglemma) widerspricht.