Stopnja grafa
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 .

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 

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 

 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 

Teorija grafov
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 \ . 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 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 točka , ki ima stopnjo enako se imenuje izolirana točka . točka , ki ima stopnjo 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č Funkcionalno je graf posebni primer psevdogozda , če ima vsaka točka izhodno stopnjo neusmerjeni povezani graf ima Eulerjevo pot , če in samo , če imaalitoč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 Teorija grafov