MEGOLDÁS:

A II/1. feladat gráfelméleti nyelven a következőképpen szól:

TÉTEL:

1. Ha egy véges egyszerű gráfban minden pont foka legalább kettő, akkor a gráf tartalmaz kört.

Vagy átfogalmazva az állítást:

1’. Ha egy véges egyszerű gráfban nincs kör, akkor van izolált pontja vagy elsőfokú pontja.

Ha egy körmentes gráfból elhagyjuk az izolált pontokat, akkor is körmentes marad. Ha nem csupa izolált pontból áll, akkor marad még pont benne, s ezek között is kell lennie izolált pontnak vagy elsőfokú pontnak. De az izolált pontokat már elhagytuk, tehát van elsőfokú pont a gráfban. A következő állítást kapjuk:

1’’. Ha egy véges egyszerű gráfban nincs kör és van éle, akkor van elsőfokú pontja.

Ez az állítás élesíthető: lásd a 39a feladatot és a 39b feladatot!

Az 1. állítás is tovább pontosítható: lásd a III. fejezet 1. feladatát!

TOVÁBB: 2. feladat
TARTALOMJEGYZÉK