第4問

$v$ を除去する；帰納法の仮定により残りのグラフは高々 $57$ 個の有効な組に分けられる。頂点 $v$ は元のグラフで入次数・出次数ともに高々 $28$ なので、他の頂点と高々 $56$ 個隣接し、$57$ 個の組のうち高々 $56$ 個を占める。したがってその隣接点を一つも含まない組が存在し、そこに $v$ を配置できて帰納法が完了する。よって $57$ 個の組は常に十分であり、$k=57$ である。