Fokszám fogalma, tételek

A gráf egy pontjába összefutó élek számát a pont fokszámának(röviden fokának) nevezzük.

Az ábrán az A pont fokszáma 2, a B ponté 3, a C ponté 4, a D ponté 5, az E ponté 3, az F ponté 1, a G ponté 0.

Már ezekből az alapfogalmakból következik, hogy egy gráfnál az élek száma és a pontok fokszámának összege között összefüggés van. Ha összeszámoljuk a gráf minden pontjánál a fokszámokat, akkor minden élt mindkét végpontjánál figyelembe vettünk. Mivel a pontok fokszámát az ott összefutó élek száma határozza meg, fennáll a következő állítás:

Tétel: Bármely gráfban a fokszámok összege az élek számának kétszerese.

Természetes, hogy olyan gráf is van, amelynek valamelyik pontjánál a fokszám páratlan. Az előző tétel szerint a fokszámok összegepáros szám, így következik belőle az alábbi állítás:

Tétel: Bármely gráfban a páratlan fokszámú pontok száma páros.