>>663
k+1個頂点抜いていいって話なら、抜いたグラフをG'として
G'ではdeg(u)+deg(v)≥nになるんだっけか?