Задача на графы В графе 9 вершин. Его ребра окрашены в два цвета так, что нет одноцветных треугольников. Какое максимальное число ребер в нем может быть?

Предыдущий
вопрос Следующий
вопрос

Предположим, что в графе 9 вершин окрашены все возможные рёбра в два цвета таким образом, что нет одноцветных треугольников.

Если мы построим граф таким образом, что каждая вершина соединена с другими 4 вершинами, мы получим максимальное количество рёбер. Таким образом, каждая вершина имеет степень 4, а общее количество рёбер равно (\frac{4 \cdot 9}{2} = 18).

Итак, максимальное количество рёбер в графе из 9 вершин составляет 18.