Как последовательность степеней вершин связана с теоремой Эрдёша-Галлаи?

Теорема Эрдёша — Галлаи устанавливает связь между последовательностью степеней вершин и графами. 13

Последовательность степеней вершин неориентированного графа — это невозрастающая последовательность, образованная степенями всех вершин графа. 1 Такая последовательность является инвариантом графа, то есть у изоморфных графов она одинакова. 1 Однако последовательность степеней вершин не является уникальной характеристикой графа: в некоторых случаях неизоморфные графы также обладают одинаковой последовательностью. 1

Теорема Эрдёша — Галлаи утверждает, что невозрастающая последовательность может быть последовательностью степеней простого графа только если: 1

• её сумма чётна; 1
• выполняется определённое неравенство. 13

Например, последовательность (3, 3, 3, 1) не может являться последовательностью простого графа: она удовлетворяет неравенству Эрдёша — Галлаи только при k, равном 1, но не при k, равном 2 или 3. 1