Graph (k - 1) -zusammenhängend einen k-zusammenhängende Graph Vertrags

Question

Ich brauche Hilfe erweist sich dieses Problem:

Sei G eine k-zusammenhängende Graph sein. Zeigen Sie, dass, wenn G 'aus einem Graphen G durch Zusammenziehen einer Kante erhalten wird, G' (k - 1) verbunden ist.

Answer 1

Nehmen wir an, Sie Knoten X.

Nehmen wir nun an G unter Vertrag‘nicht (k-1) verbunden ist. Das heißt, es gibt die Knoten {A1, A2, ..., A (k-2)}, mit denen Sie den Graphen trennen können.

Dann, selbst wenn der Knoten X mit jedem Knoten in G verbunden war, führt das Entfernen der Knoten {A1, A2, ..., A (k-2), X} zum Trennen von G. Daher ist der ursprüngliche Graph G nicht k-verbunden, was der ursprünglichen Aussage widerspricht, die den Beweis beendet.