Теорема Эрдёша — Галлаи

Теорема Эрдёша — Галлаи (критерий Эрдёша — Галлаи) — утверждение в теории графов, задающее условие, при котором конечной последовательности натуральных чисел можно сопоставить степени вершин некоторого графа. Такие последовательности чисел называются графическими. Теорема доказана венгерскими математиками Палом Эрдёшем и Шаблон:Нп2 в 1960 году.

Формулировка

Для формулировки утверждения вводятся следующие определения:

• правильная последовательность — последовательность натуральных чисел длины $n$, удовлетворяющая следующим условиям:
  1. $n-1\ge d_1\ge d_2\ge \dots \ge d_n$,
  2. $\sum _{i=1}^n{d}_i$ — чётное число;
• графическая последовательность чисел — последовательность $(d_1,d_2,\dots ,d_n)$ целых неотрицательных чисел такая, что существует граф, последовательность степеней вершин которого совпадает с ней.

Теорема утверждает, что правильная последовательность $(d_1,d_2,\dots ,d_n)$ является графической тогда и только тогда, когда для каждого $k$, $1\le k\le n-1$, верно неравенство:

$\sum _{i=1}^k{d}_i\le k(k-1)+\sum _{i=k+1}^{n}min\{k,d_i\}$.

Алгоритмизация

Построить граф по графической последовательности можно полиномиальным алгоритмом, который строится на основании критерия Гавела — Хакими.

Литература

• Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. — М.: Наука, 1990.