Посмотрите на картинку. Вершины графа слева изображают школьников одного класса. Вершины справа — предметы, в которых эти школьники показали хорошую осведомленность. Для отправки на олимпиаду нужно выбрать команду из как можно меньшего числа участников, чтобы в ней был специалист по каждому предмету.
Для выбора участников кликните на соответствующие вершины.
Заметим, что четвёртая и шестая вершина в правой доле (четвёртый и шестой предметы) соединены каждая ровно с одной вершиной в левой доле (каждый из этих двух предметов известен ровно одному ученику). Значит, эти вершины (ученики) обязательно должны быть взяты в команду.
Выбранные два ученика покрывают все предметы, кроме второго и седьмого. Но для второго и седьмого предметов не существует общего ученика, которому они оба были бы известны. Значит, минимальное необходимое количество учеников - четыре. Подходят, например, второй, четвёртый, шестой и седьмой ученики.
Ответ: минимальное необходимое количество учеников равно 4.