Ein einfacher Graph muss mindestens ein Knotenpaar mit gleichem Grad haben.

Ich bin während des Studiums der Graphentheorie auf diesen Beweis gestoßen, und obwohl er instinktiv Sinn macht, habe ich ein Problem mit einem Teil davon.

Proposition: Ein nicht-trivialer einfacher Graph G muss mindestens ein Knotenpaar mit gleichem Grad haben.

Beweis: Let G sei ein Graph mit N Eckpunkte. Weil G ein einfacher Graph ist, dann enthält er per Definition keine Mehrfachkanten oder Schleifen. Daher scheint es zu geben N mögliche Gradwerte für jeden Scheitelpunkt, nämlich 0 , . . . , N − 1 . Es kann jedoch nicht sowohl eine Ecke vom Grad 0 als auch eine Ecke vom Grad geben N − 1 , da das Vorhandensein eines Knotens vom Grad 0 impliziert, dass jeder der verbleibenden N − 1 Scheitelpunkte ist höchstens benachbart N − 2 andere Eckpunkte. Daher die N Ecken von G höchstens realisieren kann N − 1 mögliche Werte für ihre Grade [Dies ist der Teil, wo ich Probleme habe]. Das Schubladenprinzip impliziert also, dass mindestens zwei der N Ecken haben gleichen Grad.

Basiert dieser Beweis nicht auf der Annahme, dass es einen Knoten mit Grad gibt? 0 . Was passiert, wenn dies nicht der Fall ist? Hält der Beweis noch? Und warum kann das N Knoten des Graphen höchstens realisieren N − 1 mögliche Werte? Ich verstehe diesen Schritt nicht.

Antworten (3)

Nein, es gibt keine Annahme, dass der Graph einen Gradknoten hat 0 : Es gibt einfach die Beobachtung, dass es für einen Graphen unmöglich ist N Scheitelpunkte, um beide einen Scheitelpunkt des Grades zu haben 0 und ein Scheitelpunkt des Grades N − 1 . Wenn G hat einen Scheitel v Grad N − 1 , dieser Scheitel grenzt an alle anderen an N − 1 Ecken von G , und daher haben alle diese Ecken mindestens Grad 1 , weil sie alle einen Vorteil haben v . Daher, G kann nicht beide einen Scheitelpunkt des Grades haben N − 1 und ein Scheitelpunkt des Grades 0 .

Das bedeutet, wenn G hat einen Gradknoten N − 1 , die einzigen anderen möglichen Grade seiner Ecken sind 1 , 2 , … , N − 2 : Grad 0 Ist nicht möglich. Somit kann es höchstens die haben N − 1 verschiedene Grade 1 , … , N − 1 . Und wenn es einen Scheitelpunkt des Grades hat 0 , die einzigen anderen möglichen Grade seiner Ecken sind 1 , 2 , … , N − 2 : Grad N − 1 Ist nicht möglich. In diesem Fall kann es höchstens die N − 1 Grad 0 , … , N − 2 .

Und natürlich wenn G hat weder einen Scheitelpunkt des Grades 0 noch ein Scheitelpunkt des Grades N − 1 , die einzig möglichen Grade seiner Ecken sind 1 , … , N − 2 , so dass es höchstens diese haben kann N − 2 Grad.

Dann in jedem Fall G kann höchstens haben N − 1 unterschiedliche Grade für seine N Ecken, und das Schubfachprinzip sagt uns sofort, dass zwei der Ecken den gleichen Grad haben müssen.

Wow, ganz einfach, wenn man es so formuliert. Danke für die Klarstellung.
@Marwan: Gern geschehen.

Es gibt N Scheitelpunkte und es gibt N mögliche Abschlüsse: 0 , 1 , … , N − 1 . Wenn keine zwei Ecken denselben Grad haben, muss jeder mögliche Grad erreicht werden. Insbesondere muss es einen Scheitelpunkt geben v Grad 0 und ein Scheitel w Grad N − 1 . Wenn N > 1 , das ist ein Widerspruch

Betrachten Sie zwei Fälle:

  1. Es gibt einen Scheitelpunkt des Grades 0 . Dann sind die anderen Abschlüsse drin 0 , 1 , … , N − 2 . Also die Abschlüsse N Elemente von 0 , 1 , … , N − 2 was Größe hat N − 1 . Daher fallen zwei der Grade zusammen.

  2. Es gibt keinen Gradknoten 0 . Dann sind die anderen Abschlüsse drin 1 , … , N − 2 , N − 1 . Also die Abschlüsse N Elemente von 1 , … , N − 1 was Größe hat N − 1 . Daher fallen zwei der Grade zusammen.

Ein einfacher Graph muss mindestens ein Knotenpaar mit gleichem Grad haben.
AntwortenHierDatenschutz-Bestimmungen1y, 0v