IMO 2020
問題 4

$k=n(n-1)$ のとき，「どの $2$ 駅もどちらかの会社では繋がれていない」という構成ができます．

$k=n(n-1)+1$ のとき，「ある $2$ 駅があってどちらの会社でも繋がれている」が必ず成り立ちます．