Stelling van Erdős en Gallai

De stelling van Erdős en Gallai is een stelling uit de grafentheorie. Ze geeft noodzakelijke en voldoende voorwaarden opdat met een eindige lijst van natuurlijke getallen een enkelvoudige, niet-gerichte graaf kan gemaakt worden, waarvan de graden van de knopen overeenstemmen met de getallen in de lijst. Dergelijke lijst, gerangschikt in niet-stijgende volgorde, noemt men een "grafische lijst". Een graaf met overeenstemmende graden noemt men een realisatie van de lijst.

Niet elke willekeurige lijst van natuurlijke getallen is een grafische lijst. Zo moet om te beginnen de som van de getallen in de lijst even zijn: elke zijde wordt immers tweemaal geteld, eenmaal bij de beginknoop en eenmaal bij de eindknoop.

De stelling werd in 1960 gepubliceerd door Paul Erdős en Tibor Gallai in een Hongaars tijdschrift.

Stelling

Een niet dalende rij van $n$ natuurlijke getallen $d_1\ge \dots \ge d_n$ stelt de graden van een eindige enkelvoudige graaf met $n$ knopen voor als en slechts als $d_1+\dots +d_n$ even is en voor elke $k$ met $1\le k\le n$ geldt dat

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

Er bestaan verschillende bewijzen van deze stelling, waaronder een constructief bewijs waarin een graaf wordt geconstrueerd met de gegeven lijst.

Voorbeeld

We willen nagaan of de rij (3,3,3,1) een grafische lijst is. De som van de getallen is even. Is er ook aan de tweede voorwaarde voldaan?

• $k=1:3\le 1\times 0+[\min (3,1)+\min (3,1)+\min (1,1)]$ of $3\le 1+1+1$? Ja

• $k=2:3+3\le 2\times 1+[\min (3,2)+\min (1,2)]$ of $6\le 2+2+1$? Neen

• $k=3:3+3+3\le 3\times 2+\min (1,3)$ of $9\le 7$? Neen

• $k=4:3+3+3+1\le 4\times 3$? Ja.

(3,3,3,1) is dus geen grafische lijst; het is onmogelijk om een enkelvoudige graaf te construeren met 4 knopen waarvan de graden gegeven zijn door de rij (3,3,3,1).