Существует ли граф на 9 вершинах, степени которых равны 1, 1, 1, 1, 1, 2, 4, 5, 6?
Теорема Эрдёша — Галлаи
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), не выполняется.
Значит данная последовательность не является графической, по ней нельзя построить простой граф.
конкретно здесь можно измыслить так:
вершины 4, 5, 6, даже если соединены друг с другом попарно (на что уйдет 6 степеней), всё равно имеют 9 свободных степеней, которые не накрываются остальными вершинами.

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