Definiţie: Se numeşte graf neorientat o pereche ordonată de mulţimi G=(X, U), unde: X = {x1, x2, x3, …, xn} este o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U o mulţime finită de perechi neordonate de forma (xi, xj), unde i≠j şi xi, xj∈X, numite muchii. O muchie uneşte două noduri.
X = mulţimea nodurilor sau vârfurilor, iar U = mulţimea muchiilor grafului G.
Un vecin al unui vârf este orice vârf care este adiacent lui în graf.
O muchie u∈U este deci o submulţime {x, y} de vârfuri distincte din X şi se notează u = [x, y].
x şi y sunt adiacente în G, iar u şi x sunt incidente la fel ca u şi y. x şi y se numesc extremităţile
muchiei u.
Dacă u1 şi u2 sunt 2 muchii care au o extremitate comună, ele se numesc incidente.
Mulţimea muchiilor are proprietatea de simetrie, deoarece [x, y]∈U dacă şi numai dacă
[y,x]∈U.
Definiţie: Gradul unui vârf x este numărul muchiilor incidente cu x. Se notează cu d (x) (d =
degree).
Un vârf care are gradul 0 (deci pentru care nu există vreo muchie incidentă cu el) se numeşte
vârf izolat. Un vârf care are gradul 1 (deci care este incident cu o singură muchie) se numeşte vârf
terminal
Propozitie:
Fie un graf neorientat cu n noduri şi m muchii. Dacă notăm cu d1, d2, d3, …, dn gradele celor n
noduri, atunci avem relaţia:
d1 + d2 + d3 + … + dn = 2m
Corolar:
În orice graf neorientat, G=(V, M), există un număr par de vârfuri de grad impar.