Schachfiguren/Planarer Graph/Aufgabe/Lösung

Zum Turm betrachten wir die ${}5$ Felder einer fixierten Zeile, die alle untereinander durch einen Turmzug erreichbar sind. Das ist also ein vollständiger Untergraph mit ${}5$ Knotenpunkten. Nach Beispiel ist dieser nicht planar und daher ist auch der Spielzuggraph zum Turm nicht planar. Für den Läufer betrachten wir ${}5$ Felder auf der Hauptidagonalen (oder Hauptnebendiagonalen). Dies ist ebenfalls ein vollständiger Graph mit ${}5$ Knotenpunkten und somit nicht planar. Der Spielzuggraph zur Dame ist aus dem gleichen Grund nicht planar.

Der Spielzuggraph zum König ist ebenfalls nicht planar. Er besitzt ${}56$ horizontale Kanten, ${}56$ vertikale Kanten und ${}2\cdot 49$ diagonale Kanten. Deshalb gibt es insgesamt ${}210$ Kanten. Bei einem planaren Graphen mit ${}64$ Knoten darf es aber nach Fakt  (1) höchstens

${}3\cdot 64-6=186\,$

Kanten geben.

Zur gelösten Aufgabe