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  natuurlijke getallen  stelt de graden van een eindige enkelvoudige graaf met  knopen voor als en slechts als  even is en voor elke  met  geldt dat
 

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?
 of ? Ja

 of ? Neen

 of ? Neen

? 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).

Grafentheorie
Erdös-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 ingepubliceerd door Paul Erdős en Tibor Gallai in een Hongaars tijdschrift . Stelling Een niet dalende rij van natuurlijke getallen stelt de graden van een eindige enkelvoudige graaf met knopen voor als en slechts als even is en voor elke met geldt dat 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 rij3,3,1 ) een grafische lijst is . De som van de getallen is even . Is er ook aan de tweede voorwaarde voldaan ? of ? Ja of ? Neen of ? Neen ? Ja. ( 3,3,3,1 ) is dus geen grafische lijst ; het is onmogelijk om een enkelvoudige graaf te construeren metknopen waarvan de graden gegeven zijn door de rij3,3,1 ) . Grafentheorie Erdös-Gallai