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

Существует только граф со степенями вершин 0, 4, 4, 6.

Как это проверить

1. Сумма степеней всех вершин должна быть чётной.
   Это следствие того, что каждое ребро даёт по единице в степень двух вершин.
   Проверяем суммы:

   • \(1+1+7+3=12\) — чётная;
   • \(0+4+4+6=14\) — чётная;
   • \(2+3+9+11=25\) — нечётная;
   • \(1+1+1+2=5\) — нечётная;
   • \(2+2+2+3=9\) — нечётная.
     Три последних варианта сразу отпадают.

2. Для оставшихся проверяем «крайнюю» вершину.
   Если разрешены кратные рёбра (мультиграф без петель), то наибольшая степень не может превышать сумму всех остальных степеней — иначе самой «активной» вершине не хватит партнёров.

   • Для \(1,1,7,3\): max \(=7\), сумма остальных \(=1+1+3=5\). \(7>5\) — граф не существует.
   • Для \(0,4,4,6\): max \(=6\), сумма остальных \(=0+4+4=8\). \(6\le 8\) — граф существует.

3. Пример для \(0,4,4,6\):
   Пусть вершины \(A,B,C,D\).
   \(A\) — изолирована (степень 0).
   \(D\) соединена с \(B\) тремя рёбрами и с \(C\) тремя рёбрами — степень \(D=6\).
   Добавим одно ребро \(B-C\). Тогда степень \(B=3+1=4\), степень \(C=3+1=4\).
   Всё сходится: \(0,4,4,6\).

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