Hallo
Steh vor folgendem Problem, komm einfach nicht weiter! Und zwar hab ich einen ungerichteten Graphen, der aus 6 Knoten besteht. Ich soll nun beweisen das es entweder 3 Knoten gibt wo jeder mit jedem verbunden ist (Also einen Kreis kann man sagen) oder das es 3 Knoten gibt die keinen Kreis bilden, oder es kommt beides vor.
Hat hier vielleicht jemand einen hilfreichen Tip? Wäre super
Das Problem scheint mir ohne genauere Angaben kaum diskutierbar…
… einen ungerichteten Graphen, der aus 6 Knoten
besteht.
Es gibt viele Arten, wie ein Graph aus 6 Knoten besteht… ist das beliebig angenommen in der Aufgabe?
Ich soll nun beweisen das es entweder 3 Knoten gibt
wo jeder mit jedem verbunden ist (Also einen Kreis kann man
sagen) oder das es 3 Knoten gibt die keinen Kreis bilden, oder
es kommt beides vor.
Was soll heißen „…daß es…gibt“ ? sollst du die Isomorphie zeigen oder was?
Gruß
M.
Du meinst nicht drei Knoten, die keinen Kreis bilden (sonst tivial) sondern eine unabhaengige Menge der Groesse 3.
Die allgemeine Lösung liefert der Satz von Ramsay (ist aber recht kompliziert). Er besagt, dass es zu jedem Tripel (n,p,t) eine Zahl N gibt, so dass fuer jede t-Färbung der p elementigen Teilmengen einer N elementigen Menge mindestens eine Untermenge der Groesse
n nur Teilmengen einer Farbe induziert.
Fuer deinen Fall gibt es aber einen direkten Beweis. Er koennte vielleicht im Buch von Diestel stehen ?
MFG
Martin
[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]
Doch nichrt in Diestel
Sorry, im Diestel stehts doch nicht drin.
Ich meine mich dunkel zu erinnernm, dass es uns in der Vorlesung
mit einer anderen Knotentzahl vorgefuehrt wurde und wir es als Uebung dann auch mit 6 zeigen sollten. Aber wie das ging… echt keine Ahnung mehr.
Martin