В задаче надо найти максимальное независимое множество. Но есть несколько вопросов.

1) Объясните почему граф двудольный?

2) Объясните теорему Кёнинга, максимальное паросочетание = максимальное независимое множество в двудольном графе?

Ссылка на задачу

Заранее спасибо.