Существует ли граф на 9 вершинах, степени которых равны 1, 1, 1, 1, 1, 2, 4, 5, 6?

Question

[Viva8888]

Правильно ли мое доказательство? Что делать для больших последовательностей? Какой алгоритм док-ва таких задач?
Доказываю следующим образом.
Допустим, что у всех вершин степень равна 0
0 0 0 0 0 0 0 0 0
Тогда чтобы получить вершину со степенью 6 нам нужно добавить ребра
0 0 1 1 1 1 1 1 6
Здесь я соединил последнюю вершину с 3,4,5,6,7,8 вершинами, и у них степень увеличилась на 1
Теперь нам нужно получить вершину со степенью 5
1 1 1 1 1 2 2 5 6
Дальше нам нужно получить вершину со степенью 4
1 1 1 1 2 3 4 5 6
Противоречие

Answer 1

[Rsa97]

Теорема Эрдёша — Галлаи
1. 8 ≥ 6 ≥ 5 ≥ 4 ≥ 2 ≥ 1 ≥ 1 ≥ 1 ≥ 1 ≥ 1
2. 6 + 5 + 4 + 2 + 1 + 1 + 1 + 1 + 1 = 22
Данная последовательность является правильной.
k = 1, 6 ≤ (0 + 8), выполняется,
k = 2, 11 ≤ (2 + 9), выполняется,
k = 3, 15 ≤ (6 + 7), не выполняется.
Значит данная последовательность не является графической, по ней нельзя построить простой граф.

Comments

[Rsa97]

Viva8888, А вы теорему посмотрите, там всё написано.

[Viva8888]

Rsa97, ага читаю, спс

Answer 2

[Alexandroppolus]

конкретно здесь можно измыслить так:
вершины 4, 5, 6, даже если соединены друг с другом попарно (на что уйдет 6 степеней), всё равно имеют 9 свободных степеней, которые не накрываются остальными вершинами.

но это при условии, что нет кратных ребер (когда ребра А и Б соединены более чем одной вершиной), и петель (ребер А-А). У тебя ведь именно такой кейс?

Comments

[Viva8888]

спс. а можно как то in general, не для этого примера конкретно, а для любой последовательности?

[Viva8888]

да, кейс такой.
нет кратных ребер петель и т.д