ระดับขั้น

ระดับขั้นของจุดยอดในกราฟไม่ระบุทิศทาง คือ จำนวนเส้นเชื่อมที่ต่อกับจุดยอดนั้น ซึ่งถ้าเป็นเส้นเชื่อมที่เป็นวงวน (loop) จะต้องนับซ้ำสองครั้ง เพราะว่าเส้นเชื่อมมีจุดยอดปลาย 2 จุด ซึ่งจุดยอดปลายแต่ละจุดจะเพิ่มระดับขั้นให้กับจุดยอด

กราฟในรูปทางขวามีระดับขั้นดังนี้

เส้นเชื่อมในกราฟระบุทิศทาง จะประกอบด้วยจุดยอดปลาย 2 ประเภทคือ หัว (จุดยอดปลายที่มีลูกศร) และ หาง ระดับขั้นเข้า คือ ผลบวกของจำนวนหัวที่ชี้เข้ามา และ ระดับขั้นออก คือ ผลบวกของจำนวนหางที่ชี้เข้ามา

ระดับขั้นเข้าเขียนแทนด้วย ${\displaystyle \deg ^{+}(v)}$ และระดับขั้นออกเขียนแทนด้วย ${\displaystyle \deg ^{-}(v)}$

กราฟในรูปทางขวามีระดับขั้นดังนี้

จุดเอกเทศ

จุดยอดที่ ${\displaystyle \deg(v)=0}$ เรียกว่า จุดเอกเทศ

ใบ

จุดยอดที่ ${\displaystyle \deg(v)=1}$ เรียกว่า ใบ (leaf)

กราฟปรกติ

ถ้าจุดยอดทุกจุดในกราฟมีระดับขั้นเท่ากับ k กราฟนี้จะเรียกว่า กราฟปรกติ-k และกราฟนี้จะมีระดับขั้นเท่ากับ k

แหล่งต้นทาง

จุดยอดที่ ${\displaystyle \deg ^{+}(v)=0}$ เรียกว่า แหล่งต้นทาง (source)

แหล่งปลายทาง

จุดยอดที่ ${\displaystyle \deg ^{-}(v)=0}$ เรียกว่า แหล่งปลายทาง (sink)

ทฤษฎีบทกล่าวไว้ว่า กำหนดกราฟ ${\displaystyle G=(V,E)}$

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,.}$

จากทฤษฎีบทนี้ทำให้กล่าวได้ว่า สำหรับกราฟใดๆ จำนวนของจุดยอดที่มีดีกรีคี่จะมีเป็นจำนวนคู่เสมอ ทฤษฎีบทนี้รู้จักในอีกชื่อว่า ทฤษฎีการจับมือ. ชื่อนี้มาจากปัญหาทางคณิตศาสตร์ที่ว่าให้พิสูจน์ว่าในกลุ่มของผู้คนนั้น ผู้ที่จับมือกับคนอื่นเป็นจำนวนคี่ครั้งจะมีอยู่เป็นจำนวนคู่คนเสมอ