No.030 A

$k = 1$ のときは頂点を取り除かなくてもいいので YES である.

そうでないときは頂点 $n$ をまずひとつ取り除く. この結果, $1 \dots n-1$ の頂点が1本道でつながった状態になる.

これを $k$ 個の連結部分に分解するとき, 分割が可能な最大の $k$ は, $(n-2)/2+1 = n/2$ である.