< Schachfigur < 5x5 < König < Planarer Graph < Aufgabe

Der Spielzuggraph zum König auf einem -Feld ist nicht planar. Er besitzt horizontale Kanten, vertikale Kanten und diagonale Kanten. Deshalb gibt es insgesamt Kanten. Bei einem planaren Graphen mit Knoten darf es aber nach Fakt  (1) höchstens

Kanten geben.
This article is issued from Wikiversity. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.