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]$

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

Answer 2

Да, степени вершин в графе могут быть равны 7, 6, 5, 4, 4, 3, 3, 2.

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

В данном случае, граф может выглядеть следующим образом:

- Вершина A имеет степень 7, что означает, что из нее выходит 7 ребер или в нее входит 7 ребер. - Вершина B имеет степень 6, что означает, что из нее выходит 6 ребер или в нее входит 6 ребер. - Вершина C имеет степень 5, что означает, что из нее выходит 5 ребер или в нее входит 5 ребер. - Вершины D и E имеют степень 4, что означает, что из них выходит 4 ребра или в них входит 4 ребра. - Вершины F и G имеют степень 3, что означает, что из них выходит 3 ребра или в них входит 3 ребра. - Вершина H имеет степень 2, что означает, что из нее выходит 2 ребра или в нее входит 2 ребра.

Важно отметить, что в графе может быть множество различных ребер, и представленный выше граф является одним из возможных вариантов, в котором степени вершин соответствуют указанным значениям.