Указаны степени вершин графа. Выберите, какие из перечисленных графов существуют.

Краткий ответ: подходит только набор \(0,4,4,6\).

Как проверять

1. Каждое ребро даёт по единице в степень двух вершин, поэтому сумма всех степеней должна быть чётной: \[ \sum d_i = 2|E|. \]

2. Самая большая степень не может быть больше суммы остальных степеней: \[ d_{\max}\le S-d_{\max}. \] Иначе у одной вершины было бы больше «концов рёбер», чем могут принять все остальные вершины.

Проверяем варианты:

• \(2,2,2,3\): сумма \(9\) — нечётная, графа нет.
• \(2,3,9,11\): сумма \(25\) — нечётная, графа нет.
• \(1,1,7,3\): сумма \(12\) чётная, но \(7>1+1+3=5\), графа нет.
• \(0,4,4,6\): сумма \(14\) чётная, \(6\le4+4+0=8\) — граф существует.
• \(1,1,1,2\): сумма \(5\) — нечётная, графа нет.

Пример для \(0,4,4,6\): возьмём вершины \(A,B,C,D\). Проведём 3 ребра \(A\)—\(B\), 3 ребра \(A\)—\(C\) и 1 ребро \(B\)—\(C\). Вершину \(D\) оставим изолированной. Тогда: \[ d_A=3+3=6,\quad d_B=3+1=4,\quad d_C=3+1=4,\quad d_D=0. \] Получили набор \(6,4,4,0\), то есть \(0,4,4,6\).

Здесь используются кратные рёбра. Если в вашем курсе рассматриваются только простые графы, то ни один из пяти наборов не подходит: например, в простом графе на 4 вершинах степень не может быть больше 3.