Bài 4

Để chứng minh $57$ nhóm luôn đủ, dựng đồ thị có hướng phụ $H$ trên cùng $2016$ thành phố với một cạnh từ $u$ đến $v$ mỗi khi $u$ có thể đến được từ $v$ bằng nhiều nhất $28$ chuyến bay trong $G$. Vì $G$ có bậc ra bằng $1$ ở mọi nơi, mỗi đỉnh có nhiều nhất $28$ láng giềng ra trong $H$ (một cho mỗi số chuyến bay từ $1$ đến $28$). Việc chia các thành phố thành $57$ nhóm không có cạnh $H$ nào bên trong một nhóm sẽ giải quyết bài toán gốc.