Schachfigur/5x5/König/Planarer Graph/Aufgabe/Lösung

Der Spielzuggraph zum König auf einem ${}5\times 5$-Feld ist nicht planar. Er besitzt ${}20$ horizontale Kanten, ${}20$ vertikale Kanten und ${}2\cdot 16$ diagonale Kanten. Deshalb gibt es insgesamt ${}72$ Kanten. Bei einem planaren Graphen mit ${}25$ Knoten darf es aber nach Fakt  (1) höchstens

${}3\cdot 25-6=69\,$

Kanten geben.

Zur gelösten Aufgabe