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

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

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

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

• её сумма чётна; web.archive.org
• выполняется определённое неравенство. web.archive.org ru.ruwiki.ru

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