Definiţie Gradul unui vârf x este numărul muchiile incidente cu x. Gradul vârfului x se notează d(x).

Definiţie Un vârf care are gradul 0 se numeşte vârf izolat.

Definiţie Un vârf care are gradul 1 se numeşte vârf terminal.

Propoziţie Dacă un graf G(V,U) are m muchii şi n vârfuri, iar V={x1,x2,...,xn} atunci d(x1)+d(x2)+...+d(xn)=2*m.

Corolar În orice graf G există un număr par de vârfuri cu grad impar.

Definiţie Se numeşte graf complet cu n vârfuri un graf care are proprietatea că orice două noduri diferite sunt adiacente.

Propoziţie Un graf complet Kn are n(n-1)/2 muchii.

Definiţie Un graf G=(V,U) se numeşte bipartit dacă există două mulţimi nevide A, B astfel încât V=A U B, A∩B = şi orice muchie a lui G are o extremitate în A iar cealaltă în B.