На рисунке изображён двудольный граф. Какое максимальное число рёбер можно дорисовать, чтобы граф оставался двудольным?
Ну во-первых, на первый взгляд возникает сомнение в двудольности данного графа. Их нужно развеять.
Вроде ничего не изменилось, но двудольность стала очевидной.
Получается, что для максимального количества ребер в графе нужно каждую из 5 вершин в красной доле соединить с каждой из 10 в зеленой.
Получится 50 ребер, но 14 уже есть, значит остается дорисовать 36.
Ответ: 36