Sei G ein Graph mit maximalem Grad 3
Beweisen Sie, dass seine Scheitelpunkte durch 2 Farben gefärbt werden können (jeder Scheitelpunkt erhält eine Farbe), so dass es keinen Pfad der Länge zwei gibt, dessen 3 Scheitelpunkte alle dieselbe Farbe haben.
Antworten
Die Aussage gilt auch für unendliche Graphen. Es reicht aus, es für endliche Graphen zu beweisen; Der unendliche Fall kann aus dem endlichen Fall abgeleitet werden, indem einer der Beweise des De Bruijn-Erdő-Theorems nachgeahmt wird .
Lassen $G$sei ein endlicher Graph. Unter allen Scheitelpunktfarben von$G$Wählen Sie mit zwei Farben, blau und rot, eine aus, die die Anzahl der "schlechten Kanten" minimiert, dh Kanten, die zwei Scheitelpunkte derselben Farbe verbinden. Ich behaupte, dass diese Färbung macht, was Sie wollen.
Nehmen wir für einen Widerspruch an, dass es einen Pfad der Länge zwei gibt, dessen Kanten alle dieselbe Farbe haben, beispielsweise blau. Mit anderen Worten, es gibt einen blauen Scheitelpunkt$v$welches (mindestens) zwei blaue Nachbarn und höchstens einen roten Nachbarn hat. Wenn wir die Farbe von ändern$v$von blau nach rot verlieren wir dann mindestens zwei schlechte Kanten, während wir höchstens eine neue schlechte Kante erwerben. Somit hat die neue Färbung weniger schlechte Kanten als zuvor, was der Tatsache widerspricht, dass die ursprüngliche Färbung die Anzahl der schlechten Kanten minimiert.
Starke Induktion der Anzahl der Eckpunkte $n$. Die Aussage ist wahr, wenn$n = 1, 2, 3$.
Lassen $G$ haben $n$ Eckpunkte und nehmen an, dass die Aussage für Diagramme mit gilt $k$ Eckpunkte für $k<n$. Sie können jetzt annehmen$G$ ist verbunden, als ob es nicht verbunden ist, jede Komponente hat eine streng geringere Anzahl von Scheitelpunkten und Sie können sie entsprechend einfärben.
Wenn $G$ hat einen Scheitelpunkt $v$ Grad $1$, dann löschen Sie es, Farbe $G\setminus\{v\}$passend. Lassen$w$ sei der Nachbar von $v$, geben $v$ die Farbe unterscheidet sich von der von $w$ und du bist gut zu gehen.
Wenn nicht, hat jeder Scheitelpunkt einen Grad von mindestens 2, daher $G$ hat einen Zyklus $C$. Färben Sie die Eckpunkte von$C$ abwechselnd so dass $C$ hat keinen Pfad der Länge $2$ wobei alle Eckpunkte die gleiche Farbe haben.
Entfernen $C$und färben Sie die Komponenten von $G\setminus C$. Jetzt beim Beitritt$C$ Zurück, nehmen wir einen Scheitelpunkt an $v\in C$ ist mit einem Scheitelpunkt verbunden $w$ in Komponente $K$, und das $v$ist rot gefärbt. Tauschen Sie die Farben von$K$ (so wird rot blau und blau wird rot) falls nötig damit $w$ ist blau gefärbt und dann mit verbinden $v$. Auf diese Weise gibt es keinen "schlechten Weg"$K$ und es kann keinen schlechten Pfad geben, an dem zwei Eckpunkte beteiligt sind (einschließlich $v$) von $C$ und einer von $K$ oder zwei Eckpunkte von $K$ und $v$. So,$G$ hat keinen "schlechten Weg".
EDIT: Es scheint ein Fehler zu sein, da ich die Tatsache, dass der maximale Grad 3 ist, nicht ausgenutzt habe . Überprüfen Sie auf jeden Fall Grafik, zwei Farben, keine Pfadlänge 3
Sie benötigen eine maximale Bedingung für Grad 3, da nur dann a $v\in C$ mit höchstens einem anderen Scheitelpunkt verbunden sein und das gesamte Tauschgeschäft funktioniert.