thumb|right|Graf z označenimi stopnjami v točkah. Prikazan je tudi graf s stopnjo 0. Stopnja (tudi valenca grafa) (oznaka ) točke je v teoriji grafov število povezav, ki so vezane na točko. Pri tem se zanke štejejo dvakrat. Stopnjo točke se označuje z . Največja stopnja točke grafa je označena z . Najmanjša stopnja točke grafa je označena z .
Lema o rokovanju
Lema o rokovanju pravi, da je za graf dvojno število povezav enako vsoti vseh stopenj točk v grafu. To se zapiše kot:
kjer je:
stopnja točke število povezav v grafu.
Neusmerjeni grafi
V neusmerjenih grafih je stopnja v grafih brez večkratnih povezav enaka številu sosedov točk, v grafih, ki vsebujejo večkratne povezave, pa je v vsaki točki enaka vsoti števila večkratnih povezav, ki so povezane s točko (so incidentne s točko).
Usmerjeni grafi thumb|right|Usmerjeni graf z vpisanimi stopnjami za točke: (vhodna stopnja, izhodna stopnja).
V usmerjenem grafu ima vsaka povezava začetek in konec. Zaradi tega se lahko za vsako točko določi vhodno stopnjo (oznaka ) in izhodno stopnjo (oznaka ). Če se obravnava graf z večkratnimi povezavami, je: vhodna stopnja v grafih brez večkratnih povezav enaka številu sosednjih vozlišč. v grafih z večkratnimi povezavami v vsaki točki vhodna stopnja enaka vsoti števila vseh vstopajočih povezav. izhodna stopnja v grafih brez večkratnih povezav enaka številu sosednjih točk. izhodna stopnja v grafih z večkratnimi povezavami v vsaki točki enaka vsoti števila vseh izstopajočih povezav.
Posebni primeri thumb|right|Neusmerjeni graf z listi, ki pripadajo točkam 4, 5, 6, 7, 10, 11 in 12
Točka, ki ima stopnjo enako 0, se imenuje izolirana točka. Točka, ki ima stopnjo 1, se imenuje list.
Nekatere značilnosti
Če ima vsaka točka grafa enako stopnjo, je graf k-regularen. V tem primeru ima graf stopnjo k. Usmerjeni graf je psevdogozd, če in samo če ima vsaka točka izhodno stopnjo največ 1. Funkcionalno je graf posebni primer psevdogozda, če ima vsaka točka izhodno stopnjo 1. Neusmerjeni povezani graf ima Eulerjevo pot, če in samo, če ima 0 ali 2 točki s liho stopnjo. Kadar nima vozlišč z liho stopnjo je Eulerjeva pot Eulerjev krog. Po Brooksovem izreku je v vsakem povezanem neusmerjenem grafu z največjo stopnjo kromatično število grafa največ enako , razen, če je graf klika ali sodi cikel, v tem primeru pa je kromatično število enako . Po Vizingovem izreku ima vsak graf kromatično število enako . k-izrojen je graf v katerem ima vsak podgraf točko s stopnjo največ .
Zunanje povezave
Osnove teorije grafov Uvod v teorijo grafov Stopnja (teorija grafov) – video
Kategorija:Teorija grafov