回答
[id:lethevert:20070124:p4]
帰納法。
Nノードのグラフは、任意のk(0<k<N)に対し、kノードのグラフと(N-k)ノードのグラフに分割することができて、それぞれ辺を1つ取り除くと連結ではなくなり、2つのグラフ間はただ1つの辺で連結している。
[id:lethevert:20070124:p4]
帰納法。
Nノードのグラフは、任意のk(0<k<N)に対し、kノードのグラフと(N-k)ノードのグラフに分割することができて、それぞれ辺を1つ取り除くと連結ではなくなり、2つのグラフ間はただ1つの辺で連結している。