Maksimal knudevalens

Alle knuderne i en graf G = (V, E) har en given valens. Lad v ∈ V være den knude med maksimal valens, dvs. ${\displaystyle \delta _{v}}$ ≥ ${\displaystyle \delta _{u}}$ for alle u ∈ V, hvor knuden u ≠ v. Den maksimale knudevalens Δ(G) for G er lig tallet ${\displaystyle \delta _{v}}$. Med andre ord det er det tal der angiver valensen på den knude, som er størst blandt valensen af de andre knuder i G.