Niedriggradige Knoten in spärlichen Graphen

7

Sei ein Graph mit Eckpunkten, von denen keiner isoliert ist, und Kanten, wobei . Zeigen Sie, dass mindestens zwei Eckpunkte vom Grad eins enthält.G=(V,E)nn1n2G

Ich habe versucht, dieses Problem mit der Eigenschaft zu lösen . Kann dieses Problem mithilfe des Taubenlochprinzips gelöst werden ?vVdeg(v)=2|E|

Saurabh
quelle
3
Versuchen Sie, das stärkere Ergebnis zu beweisen, wenn die Anzahl der Kanten nur weniger als beträgtn (nicht unbedingt)n1). Induktion einschaltenn. Sie können davon ausgehen, dass der Graph ohne Verlust der Allgemeinheit verbunden ist (warum?). Wenn Sie den Beweis herausfinden, veröffentlichen Sie ihn als Antwort unten.
Kaveh
Ich sehe nicht, wie sich die Verwendung des gesamten Taubenprinzips von der Verwendung dieser Identität unterscheidet.
Raphael
Ein so spärlicher Graph muss ein Baum sein, oder?
Strin
Ja, es ist ein Baum
Saurabh
1
@ SaurabhHota: Diese Einsicht kann auch als Beweis verwendet werden.
Raphael

Antworten:

7

Ja, kann es.

Du hast n1 Kanten, was bedeutet 2n2Löcher für Knotentauben. Wenn jeder Knoten einen Grad zwei (oder mehr) haben soll, müssen wir (mindestens) zwei Tauben für jeden Knoten platzieren, was insgesamt ergibt2n Tauben.

Nach diesem Prinzip finden (mindestens) zwei Tauben kein einzelnes Loch, was bedeutet, dass (mindestens) ein Knoten isoliert ist oder (mindestens) zwei Knoten nur eine Kante haben. Da kein Knoten durch Annahme isoliert ist, haben Sie (mindestens) zwei Knoten mit Grad eins.

Raphael
quelle
3

Da ist die Anzahl der Kanten n1ist der Graph ein Baum. Nehmen Sie einen Startscheitelpunktv im V.(G). Gehen Sie nun in eine beliebige Richtung und gehen Sie weiter, ohne einen Scheitelpunkt zu wiederholen. Schon seitG ist endlich und enthält keinen Zyklus, wird dieser Prozess schließlich in einem Scheitelpunkt gestoppt u Grad 1. Wenn vhatte auch grad 1, wir sind fertig. Wenn nicht, beginnen Sie einen neuen Spaziergang in eine andere Richtungv. Diese Wanderung endet auch in einem Scheitelpunkt des Grades 1.

utdiscant
quelle