Vizing-tétel | mateking
 

Vizing-tétel

A Vizing-tétel a gráfok élkromatikus számára ad alsó és felső becslést:

\( \Delta(G) \leq \chi_e(G) \leq \Delta(G) + 1 \)

Vagyis a $G$ egyszerű gráfok két osztályba sorolhatók:

Első osztály: $\chi_e(G) = \Delta(G)$

Második osztály: $\chi_e(G) = \Delta(G)+1 $