графы - Хроматическое число. Теория графов.

Граф, насколько я понимаю, считается простым.

Для того, чтобы хроматическое число было больше двух, то есть граф не оказался двудольным, необходимо наличие цикла нечётной длины. При этом трёх рёбер достаточно -- это минимальное число. Если потребовать дополнительно, чтобы граф был связным, то ответом будет 27.

Далее рассмотрим такой пример: разобьём все вершины на 3 подмножества из 9 вершин, и соединим рёбрами вершины из разных подмножеств. Рёбер станет $%3\cdot9^2=243$%. Покажем, что это количество максимально. Пусть имеется $%k_i$% вершин $%i$%-го цвета, где $%k_1+k_2+k_3=27$%. Вершины одного цвета не соединены, и рёбер имеется не более $%k_1k_2+k_1k_3+k_2k_3$%.

Складывая почленно три неравенства $%(x-y)^2\ge0$%, $%(x-z)^2\ge0$% и $%(y-z)^2\ge0$% и сокращая на 2, получаем $%x^2+y^2+z^2\ge xy+xz+yz$%. Прибавляя $%2(xy+xz+yz)$% к обеим частям, имеем $%(x+y+z)^2\ge3(xy+xz+yz)$%. Таким образом, $%k_1k_2+k_1k_3+k_2k_3\le\frac13(k_1+k_2+k_3)^2=\frac{27^2}3=3^5=243$%.