Maksimal knudevalens

Der er ingen kildehenvisninger i denne artikel, hvilket er et problem. Du kan hjælpe ved at angive kilder til de påstande, der fremføres. Hvis ikke der tilføjes kilder, vil artiklen muligvis blive slettet.

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.