Существует ли 8-вершинный граф, степени вершин которого равны (a) 8,6,5,4,4,3,2,2 (b) 7,7,5,4,4,2,2,1 (c) 7,3,3,3,3,2,2,1 (d) 6,6,6,5,5,4,4,4 (e*) 6,6,6,5,5,3,2,2

Чтобы определить, существует ли 8-вершинный граф с заданными степенями вершин, необходимо воспользоваться теорией графов, в частности, теоремой о необходимости и достаточности для существования простого связного графа с заданными степенями.

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

Теперь проверим каждое из предложенных случаев:

(a) Степени: 8, 6, 5, 4, 4, 3, 2, 2. Сумма степеней: 8 + 6 + 5 + 4 + 4 + 3 + 2 + 2 = 34 (чётное). Подходят ли подмножества? Нет, вершина со степенью 8 не может соединиться с 7 другими вершинами, так как их всего 7. Поэтому графа не существует.

(b) Степени: 7, 7, 5, 4, 4, 2, 2, 1. Сумма степеней: 7 + 7 + 5 + 4 + 4 + 2 + 2 + 1 = 32 (чётное). Проверим подмножества. Вершины со степенью 7 требуют, чтобы у них было по 7 соединений. Учитывая, что всего 8 вершин, они не могут быть соединены со всеми. Графа не существует.

(c) Степени: 7, 3, 3, 3, 3, 2, 2, 1. Сумма степеней: 7 + 3 + 3 + 3 + 3 + 2 + 2 + 1 = 24 (чётное). Вершина со степенью 7 должна соединиться как минимум с 7 другими вершинами, что невозможно. Графа не существует.

(d) Степени: 6, 6, 6, 5, 5, 4, 4, 4. Сумма степеней: 6 + 6 + 6 + 5 + 5 + 4 + 4 + 4 = 40 (чётное). Проверка подмножеств показывает, что оно подходит, так как каждая вершина может быть соединена соответственно. Граф существует.

(e*) Степени: 6, 6, 6, 5, 5, 3, 2, 2. Сумма степеней: 6 + 6 + 6 + 5 + 5 + 3 + 2 + 2 = 35 (нечётное). Поэтому графа не существует.

Таким образом, только вариант (d) соответствует необходимым условиям для существования 8-вершинного графа.