Strukturmethoden-Training

Von einem $8\times8$-Schachbrett werden zwei gegenüberliegende Eckfelder entfernt. Zeige, dass der Rest nicht mit Dominosteinen überdeckt werden kann.

Zeige, dass die Knoten eines ungeraden Kreises nicht mit zwei Farben so gefärbt werden können, dass benachbarte Knoten verschiedene Farben haben.

Unter sechs Personen sind immer drei, die sich paarweise kennen, oder drei, die sich paarweise nicht kennen. Zeige dies durch eine Zweifärbung der Verbindungslinien.

Ordne zu und begründe: A gleiche Reste unter vielen Zahlen, B unerreichbarer Spielzustand, C Endpunkt eines längsten Weges, D unmögliche Brettüberdeckung.