En teoria de grafs, el grau o valència d'un vèrtex és el nombre d'arestes que hi incideixen, amb els bucles comptats dues vegades.[1] El grau d'un vèrtex v es denota grau(v), g(v) o gr(v) (tot i que també es fa servir δ(v), i de l'anglès d(v) i deg(v)). El grau màxim d'un graf G, denotat com Δ(G), i el grau mínim d'un graf G, denotat com δ(G), són respectivament els graus màxim i mínim dels seus vèrtexs. Al graf de la dreta, el grau màxim és 3 i el grau mínim és 0. En un graf regular tots els graus són iguals, i per tant es pot parlar del grau del graf.
- ↑ Diestel, Reinhard. Graph Theory (en anglès). 3a ed.. Berlin, New York: Springer-Verlag, 2005, p.5. ISBN 978-3-540-26183-4.