Regulaarne graaf
Regulaarne graaf on graaf mille kõikide tippude valentsused (astakud) on võrdsed, st iga tipp omab sama arv naabertippe. Regulaarsuse valents on graafi invariant ning tähistatakse r ( G ) {\displaystyle r(G)} . Kõikide graafide hulgas domineerivad mitteregulaarsed, regulaarsete osakaal on kaduvväike. Kuna regulaarsete graafide raames võib esineda ka teisi regulaarsusi, siis nimetagem siin esimest valentsregulaarsuseks. Valentsuse (astaku) järgi klassifitseeritult koosneb: 0-regulaarne (tühi graaf) isoleeritud tippudest; 1-regulaarne isoleeritud servadest; 2-regulaarne isoleeritud ringidest (tsüklitest, vöödest) või kujutab tervikuna ringi. 3-regulaarset nimetatakse ka kuupgraafiks. 0-valentsregulaarne graaf 1-valentsregulaarne graaf 2-valentsregulaarne graaf 3-valentsregulaarne graaf