На рисунке изображен двудольный граф. Какое максимальное число ребер можно дорисовать, чтобы граф остался двудольным?

Answer 1

сложи его мысленно слоями так, чтобы верхня вершина оказалась в 3-м ряду, а 4-й ряд лег на 2-й ряд. Ну и проводи между рядами все недостающие ребра.

ты можешь провести 4 ребра между верхней вершиной и 4-мя вершинами 3-го ряда, и 16 между 2-м и 4-м рядом.

Answer 2

верхня вершина не должна быть в одной доле с вершинами второго ряда, второй - с третьим, и третий - с четвертым.

Поэтому вершины можно распределить по долям единственным образом: 1 и 3 ряды, 2 и 4.

В одной доле 5 вершин, в другой - 10. Между ними можно провести 50 ребер. 14 уже проведены. Остаётся 36.