Graphen-Training

Ein einfacher Graph hat 12 Knoten und 31 Kanten. Zeige, dass ein Knoten Grad mindestens 6 besitzt.

Zeige: Ein Graph mit $n$ Knoten und $e$ Kanten besitzt einen Knoten vom Grad mindestens $\lceil2e/n\rceil$.

Ein Graph mit 20 Knoten besitzt 91 Kanten. Welche Mindestgröße des maximalen Grades ist garantiert?

Zeige für jeden einfachen Graphen mit $n\ge2$ Knoten, dass zwei Knoten denselben Grad haben.

Erkläre, warum „$n$ Knoten und $n$ mögliche Grade“ noch keine Gradkollision beweist, und repariere das Argument.

In einem bipartiten Graphen hat die rechte Seite vier Knoten und die linke Seite 17 Knoten. Zeige, dass zwei linke Knoten genau dieselben rechten Nachbarn besitzen.

Zeige: Haben in einem bipartiten Graphen mehr als $2^m$ linke Knoten nur $m$ mögliche rechte Nachbarn, so besitzen zwei linke Knoten identische Nachbarschaften.

Jede Kante des vollständigen Graphen auf sechs Knoten ist rot oder blau. Zeige, dass ein einfarbiges Dreieck existiert.