Schach/3x3/König/Knotenüberdeckungszahl/Aufgabe/Lösung
Die Knotenüberdeckungszahl ist . Eine maximale Knotenüberdeckung erhält man durch den Mittelpunkt zusammen mit den vier Eckpunkten (oder den vier Seitenmittelpunkten). Wenn das Zentrum nicht zu einer Knotenüberdeckung gehört, so müssen alle acht Kanten, die vom Zentrum ausgehen, abgedeckt werden, und das wären schon acht Punkte. Eine optimale Knotenüberdeckung muss also das Zentrum beinhalten. Die verbleibenden acht Randkanten bilden einen Rundgang und man braucht vier (abwechselnde)
Punkte für die Abdeckung. Die eingangs erwähnten Überdeckungen sind also optimal.