グラフ（k - 1）私はこの問題を証明助ける必要

Question

K-連結グラフを収縮-connected：

レッツGは、k連結グラフでありますエッジを収縮させてグラフGからG 'を求めると、G'は（k-1）であることを証明する。

Answer 1

は今、G「を仮定しますが、ノードX

契約を前提とします（K-1）が接続されていません。これはノード{A1、A2、...、A（k-2）}が存在することを意味し、グラフの接続を解除することができます。

ノードGがすべてのノードに接続されていても、ノード{A1、A2、...、A（k-2）、X}を削除するとGが切断されます。 k-接続され、元の文と矛盾し、証明を終了する。