Péternek 28 osztálytásra van mint a 28-nak különböző számú barátja van az osztályban, hány barátja van közülük péternet? (a barátság kölcsönös)

A Behzard-Chartrand tetel szerint 14.

1) Ha minden osztalytarsanak van baratja:

Ha az el fokszam sorozatban egy ismetlodes van csak, akkor egy n csucsu grafban az ismetlodo j fokszamnak

n/2-1 es n/2 kozott kell lennie, beleertve a hatarokat.

Itt n=29 mert Peter is beszamit a baratsag mint relacio altal termeszetesen generalt grafba, tehat 14-nek kellene lennie az ismetlodo fokszamnak.

2) ha az egyik osztalytarsanak nincs baratja, akkor 13 es 14 is lehetseges.

A reszletes kidolgozasa a feladatnak azthiszem itt megtalalhato:

M. Behzad and G. Chartrand, No graph is perfect, Amer. Math. Monthly 74(1967), 962-963.