Feladat: 2.5.
* a) Bizonyítsuk be, hogy ha
n>1 és egy
2n pontú egyszerű gráfban több, mint
n2
él van, akkor van benne négy olyan pont, amelyek között legalább öt él fut. [
180]
b) Bizonyítsuk be, hogy
n2
él esetén a) állítás már nem mindig igaz: van olyan
n pontú,
n2
élű egyszerű gráf, amelyben bármely négy pont között legfeljebb négy él fut.
Tehát
eG
(2n)=
n2
, ahol
G a négypontú, ötélű gráf.