GráFóka nem csak egy átlagos fóka, hanem egy igazi matematikai zseni. GráFóka imádja a gráfokat, és szabadidejében a legújabb gráfelméleti problémákon dolgozik - neki a Königsbergi hidak problémája csupán gyerekjáték. Azóta GráFóka minden nap tanul valami újat a gráfokról, és alig várja, hogy megossza tudását veled is!
A gráfelmélet alapfogalma a gráf, olyan struktúra, ami csúcsokból vagy szögpontokból és élekből áll, minden él két (esetleg egybeeső) csúcs között fut.
Legtöbbször egyszerű gráfokkal foglalkozunk, azaz olyanokkal, amelyekben nincs hurokél (egy csúcsot önmagával összekötő él) és nincsenek párhuzamos élek sem, tehát azonos csúcsok között haladó különböző élek.
Egy G gráf részgráfja olyan gráf, ami G bizonyos csúcsaiból és azok között bizonyos éleiből áll.
Véges gráfok esetén a fokszámokat összeadva páros számot kapunk, hiszen ekkor minden élt kétszer számoltunk.
Ha a fokszám minden csúcsra azonos, a gráf reguláris. Ha ez a közös fokszám k, akkor a gráf k-adfokú reguláris vagy k-reguláris.
A Hamilton-kör egy, a gráf minden csúcsán pontosan egyszer áthaladó kör.
