Какое наибольшее число рёбер может быть в двудольном графе на 12 вершинах?

Для двудольного графа с n вершинами, разделенными на две доли размерами k и n-k, максимальное количество ребер достигается, когда каждая вершина из первой доли соединена со всеми вершинами из второй доли. Таким образом, максимальное число ребер равно произведению размеров долей: k * (n - k).

В нашем случае n = 12. Нам нужно найти такое k, чтобы k * (12 - k) было максимальным. Это происходит, когда k максимально близко к n/2, то есть к 6.

Если k = 6, то n - k = 12 - 6 = 6. Максимальное число ребер будет 6 * 6 = 36.