Definujte stupeň vrcholu, okolí vrcholu a regulární graf. Dále formulujte větu o principu sudosti a její důsledek pro počet vrcholů lichého stupně.

Stupeň vrcholu [ $degG(v)$ ]

• Symbolem $\text{degG}(v)$ označíme počet hran grafu $G$ obsahujících vrchol $v$

→ toto číslo nazveme stupněm vrcholu $v$ v grafu $G$

Vrchol stupně 0 nezveme izolovaný (nemá žádné sousedy)

Okolí vrcholu [ $nG(v)$ ]

• Symbolem nG(v) označíme množinu všech sousedů vrcholu v v grafu G

→ tuto množinu nazveme (otevřené) okolí v v grafu G

Regulární graf

• Graf je r-regulární pokud stupeň každého vrcholu grafu je r
• graf je regulární, pokud je r-regulární pro libovolné r

Princip sudosti