Question

Могут ли степени вершин в графе быть равны 7; 6; 5; 4; 4; 3; 3; 2 ?​

Answer 1

Длина этой последовательности 8.

$1) 8 - 1 \geq 7\geq 6\geq 5\geq 4\geq 4\geq 3\geq 3\geq 2\\2) 7 + 6+5+4+4+3+3+2 = 34$

Эти два условия означают, что последовательность правильная в смысле Эрдёша - Галлаи.

Теперь применим критерий Эрдёша-Галлаи, а именно:

Правильная последовательность является графической тогда и только тогда, когда для каждого $k, 1\leq k\leq n-1$, верно неравенство

$d_1 + ... + d_k \leq k^2 - k + (min(k, d_{k+1}) + ... + min(k, d_n))$

Проверим:

1) k = 1

7 <= 1 - 1 + 1*7

2) k = 2

7 + 6 <= 4 - 2 + 2*6

...

Если составить таблицу сумм на всех итерациях, получится следующее:

$\left[\begin{array}{cc}7&7&13&14\\18&20&22&24\\26&28&29&35&34&56\end{array}\right]$

Значит, граф с такими степенями вершин существует