Graphentheorie Beweis?
Ich will beweisen, dass wenn ein einfacher ungerichteter Graph maximal einen Kreis besitzt, der durchschnittliche Knotengrad dann höchstens 2 ist.
Mein Ansatz wäre irgendwie anzunehmen, dass der durchschnittliche Knotengrad 3 ist, und dann zu zeigen, dass der Graph dafür aber mehr als einen Kreis besitzen muss, ich weiß nur nich wie oder vielleicht ist mein Ansatz auch falsch, kann wer helfen?
2 Antworten
Ohne es zuende gedacht zu haben:
Du fängst mit einem Graph an, der genau einen Kreis hat, z.B. einen mit 3 Knoten vom Grad 2. Wenn du jetzt einen Knoten in den Kreis einfügst (zwischen zwei bestehende) haben immer noch alle den Grad 2. Machst du einen Abzweig, der nicht zu einem Kreis führt, hast du Grad 3 am Abzweigungspunkt und Grad 1 am Ende der Sackgasse.
Das musst du natürlich noch anständig ausformulieren. Liegt bei mir schon einige Zeit zurück ...
anzunehmen, dass der durchschnittliche Knotengrad 3 ist
Der Durchschnitt könnte auch 2,1 sein.
Zeige lieber direkt, dass so ein Graph nicht mehr Kanten als Knoten haben kann. Wenn Du den einzigen Kreis im Graph auftrennst (eine Kante entfernst), bleibt ein kreisfreier Graph übrig. Klingelt da was bei dir?
