Могут ли степени вершин в графе без циклов и двойных ребер быть равны: а) 6,5,4,3,2,1; б) 6,2,2,2,2,2,2. Ответ обоснуйте. Если граф существует, нарисуйте его.

Сумма степеней всех вершин графа должна быть четным числом, так как каждое ребро добавляет 2 к общей сумме степеней (по 1 к каждой из двух вершин, которые оно соединяет).

a) Проверим для набора 6, 5, 4, 3, 2, 1:

$$6 + 5 + 4 + 3 + 2 + 1 = 21$$

Сумма 21 - нечетное число. Следовательно, граф с такими степенями вершин невозможен.

б) Проверим для набора 6, 2, 2, 2, 2, 2, 2:

$$6 + 2 + 2 + 2 + 2 + 2 + 2 = 18$$

Сумма 18 - четное число. Такой граф теоретически возможен. Однако, стоит помнить, что в графе без петель и кратных рёбер, степень любой вершины не может быть больше, чем (n-1), где n - общее число вершин.

У нас 7 вершин. То есть максимальная степень вершины не может быть больше 6. Вершина со степенью 6 должна быть соединена со всеми остальными вершинами. Остальные вершины должны иметь степень 2.

Представим вершину со степенью 6 как А, а остальные вершины B, C, D, E, F, G.

Тогда, А соединена со всеми остальными. Осталось обеспечить степень 2 для вершин B, C, D, E, F, G.

Один из возможных вариантов графа: B-C, D-E, F-G.

Ответ: а) не может, так как сумма степеней вершин нечетная; б) может существовать.