グラフ理論の問題についての質問です

質問

大学のグラフ理論の問題でわからないものがあったので質問させていただきます。

******************
問題：

グラフGが位数|V(G)|=nでk個の連結成分を持つグラフの時、辺数|E(G)|が

n-k≦|E(G)|≦1/2(n-k+1)(n-k)

をみたすことを示しなさい。

*******************

以上の問題を帰納法をつかって証明しようとしたのですが、詰まってしまいました。
よろしければこの問題の証明方法を教えてください。
よろしくお願いします。

回答No.1

Tacosan

左はほぼ自明なので省略.
右は「頂点数が n1, n2 である 2つの完全グラフの辺の本数の和」よりも「頂点数が (n1+n2-1) 及び 1 である 2つの (以下略) 」の方が小さくないことを示せば OK.