Beweisen Sie, dass der Graph G doppelt zusammenhängend ist?

... komplette Frage anzeigen

1 Antwort

Naja denk doch mal nach. 

Wenn der Grad von v und w jeweils n-1 ist, müssen sie schon mal zu allen anderen Knoten adjazent sein, da |V|=n. Also müssen alle u_i mit v und w adjazent sein. Wenn du also eine Kante rauswirfst, hängen die inzidenten Knoten immer noch an irgendeinem anderen Knoten, wodurch der Graph zusammenhängend bleibt. 

Und das musst du jetzt ausführlich hinschreiben. Am besten vorher mal aufmalen, damit du weißt, was ich meine.

Antwort bewerten Vielen Dank für Deine Bewertung

Was möchtest Du wissen?