Ungerichtete Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei G = (V,E) ein einfacher ungerichteter Graph. Es gelte |E(G)| [mm] \ge [/mm] |V(G)| + 4.
Zu zeigen ist, dass G dann zwei kantendisjunkte Kreise enthalten muss. |
Hallo,
ich brauche einen Denkanstoß, wie man bei dieser Aufgabe vorgehen bzw. welchen Satz benutzen soll. Es ist klar, dass G mehrere Kreise enthalten muss, die Frage ist wie man die Kantnedisjunktheit zeigt.
Vielen Dank
P.S. Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:43 Do 18.10.2012 | | Autor: | M.Rex |
Hallo
Ein einfacher Graph mit n Knoten hat doch Maximal [mm] \frac{n(n-1)}{2} [/mm] Kanten.
Außerdem hat ein einfacher Graph keine Mehrfachkanten oder Schleifen.
Hilft das schon etwas weiter?
Marius
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:57 Fr 19.10.2012 | | Autor: | olafus |
Ich würde einen Widerspruchsbeweis konstruieren. Betrachte ein kantenminimales Gegenbeispiel .
Versuche dir folgende Aussagen in diesem Fall klar zu machen:
o.E. G zusammenhängend.
Kreise in G haben mindestens Länge 5
Alle Knoten in G haben Grad >= 3.
n>= 10.
|
|
|
|
