IMO 1990 Graph Theory Problem

Question

Also habe ich diese Lösung für IMO 1990 P2 gesehen:

Aufgabe 2: Nehmen wir n≥3 an und lassen Sie S eine Menge von 2n - 1 verschiedenen Punkten auf einem Kreis sein. Angenommen, genau k Punkte von S sind schwarz gefärbt. Eine Färbung von S heißt "gut", wenn es mindestens ein Paar der schwarzen Punkte gibt, so dass das Innere eines der Bögen zwischen dem Paar genau n Punkte von S enthält. Finden Sie den kleinsten Wert von k, so dass jede Färbung von S sei "gut".

Lösung: Betrachten Sie einen Graphen G, dessen Eckpunkte die Punkte darstellen und zwischen zwei Eckpunkten eine Kante liegt, wenn das Innere eines der von ihnen definierten Bögen genau n Eckpunkte aufweist. Wir wollen zeigen, dass beim Färben von k Eckpunkten zwei benachbarte Eckpunkte gefärbt wurden. Da der Grad jedes Scheitelpunkts 2 ist, zeigt Übung 4.1.4, dass G die Vereinigung disjunkter Zyklen ist. Beachten Sie, dass, wenn wir die Eckpunkte von 1 bis 2n - 1 nummerieren, 1 neben n + 2 und n + 2 neben 2n + 3 liegt, was Scheitelpunkt 4 ist. Somit befinden sich 1 und 4 im selben Zyklus. Wenn 2n - 1 nicht durch 3 teilbar ist, besteht G nur aus einem Zyklus, so dass k = n eindeutig die gewünschte Zahl ist. Wenn 2n - 1 durch 3 teilbar ist, wird der Graph durch drei disjunkte Zyklen der Länge 2n - 1 3 gebildet. Somit können wir höchstens 2n - 1 3 - 1 2 = n - 2 3 Eckpunkte eines Zyklus färben, ohne dass aufeinanderfolgende Eckpunkte gefärbt werden. Somit ist k = 3 · ((n - 2) / 3) + 1 = n - 1 die Zahl, die wir in diesem Fall wollen.

Ich verstehe nicht, warum es heißt, dass jeder Eckpunkt Grad 2 haben wird. Könnte mir jemand das erklären?

Answer 1

Der Grad ist die Anzahl der anderen Scheitelpunkte, mit denen jeder Scheitelpunkt Kanten verbindet. In diesem Fall werden die beiden verbundenen Eckpunkte durch Zählen von n + 1 Punkten in jeder Richtung entlang des Kreises gefunden.