С.1. а) Докажите, что не существует графа без петель и кратных ребер, у которого 5 вершин, степени которых равны 4, 1, 3, 2, 4. Ответ:

Ответ: не существует

Решение:

Предположим, что существует граф без петель и кратных ребер с 5 вершинами, степени которых равны 4, 1, 3, 2, 4.

Сумма степеней всех вершин равна: 4 + 1 + 3 + 2 + 4 = 14.

По теореме о сумме степеней вершин графа, эта сумма должна быть равна удвоенному числу ребер. То есть, 2\( \cdot \) (количество ребер) = 14.

Следовательно, количество ребер должно быть равно 14 / 2 = 7.

Максимальное число ребер в графе без петель и кратных ребер с 5 вершинами равно \(\frac{n(n-1)}{2}\), где n - число вершин. В нашем случае это \(\frac{5(5-1)}{2} = \frac{5\cdot4}{2} = 10\).

Однако, степень каждой вершины не может быть больше, чем n-1 (иначе появятся кратные ребра или петли). В данном графе есть вершины степени 4, что соответствует условию (5-1 = 4).

Проблема в том, что сумма степеней вершин должна быть четной, чтобы соответствовать удвоенному числу ребер. В нашем случае сумма степеней 14, что является четным числом. Но, если существует такая конфигурация, то число ребер должно быть целым.

Теперь рассмотрим вершину степени 1. Она должна быть связана с какой-то одной вершиной. Вершины степени 2, 3 и 4 тоже должны соответствовать своей степени.

Поскольку у нас есть две вершины степени 4, это значит, что каждая из этих вершин должна быть связана со всеми остальными четырьмя вершинами. Однако, если мы нарисуем такой граф, мы обнаружим, что невозможно выполнить все условия без создания кратных ребер или петель.

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

Таким образом, невозможно построить граф без петель и кратных ребер, удовлетворяющий заданным условиям.

Ответ: не существует