Задача по алгебре В графе 13 вершин. Степень каждой вершины либо 11 либо 4. Какое наибольшее число рёбер может быть в таком графе?

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

Пусть в графе (n) вершин степени 4 и (13-n) вершин степени 11. Тогда общее количество рёбер в графе можно выразить как

[ \frac{4n + 11(13-n)}{2} = 2n + 143 ]

Максимизируем эту функцию:

[ \frac{d}{dn} (2n + 143) = 2 ]

Исходя из этого выражения, можно заключить, что функция возрастает при увеличении (n). Следовательно, наибольшее количество рёбер будет в случае, если все вершины имеют степень 11, т.е. (n = 0). Тогда наибольшее число рёбер равно

[ 2 \cdot 0 + 143 = 143 ]

Таким образом, наибольшее число рёбер в данном графе может быть 143.