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

Introduction

The Erdős–Gallai theorem gives a necessary and sufficient condition for a sequence of non-negative integers to be the degree sequence of a simple graph.

In other words, it tells us whether a given sequence can appear as the list of vertex degrees in some graph without loops or multiple edges.

Theorem Statement

Let

d_1 \ge d_2 \ge \dots \ge d_n \ge 0

n

≥

0

be a non-increasing sequence of integers.

Then this sequence is graphical, that is, it is the degree sequence of some simple graph, if and only if:

the sum of all degrees is even;
for every $k$ such that $1 \le k \le n$ , the following inequality holds:

\sum_{i=1}^{k} d_i \le k(k-1) + \sum_{i=k+1}^{n} \min(k, d_i)

Understanding the Theorem

This theorem gives a direct way to check whether a degree sequence is valid.

The first condition is natural: in any graph, the sum of all degrees must be even, because every edge contributes 2 to the total degree.

The second condition ensures that the largest degrees can actually be realized without violating the rules of a simple graph.

Verification Algorithm

To verify a sequence using the Erdős–Gallai theorem, we can do the following:

sort the sequence in non-increasing order;
check that the sum of the degrees is even;
for every $k$ from $1$ to $n$ , check the Erdős–Gallai inequality.

A straightforward implementation works in $O(n^2)$ time.

Faster Implementation

We can do better by maintaining the left-hand side and the right-hand side of the inequality as we move from $k$ to $k+1$ .

The left-hand side can be maintained using prefix sums.
For the right-hand side, we need to know how many values are at most the current $k$ .

This can be implemented using a counting array.

bool erdos_gallai(vector<int> d) {
    int n = (int)d.size() - 1; // assume 1-indexed
    vector<int> cnt(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        cnt[d[i]]++;
    }

    sort(d.begin() + 1, d.end(), greater<int>());

    long long sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += d[i];
    }
    if (sum % 2 != 0) {
        return false;
    }

    long long left = 0, right = 0;
    int less = 0;

    for (int k = 1; k <= n; k++) {
        left += d[k];
        less += cnt[k];

        right += 1LL * k * cnt[k];
        right += 1LL * k * (n - k - less);

        if (left > 1LL * k * (k - 1) + right) {
            return false;
        }

        right -= 1LL * k * (n - k - less);
        if (d[k] <= k) {
            right--;
            less--;
        }
    }

    return true;
}