ระดับขั้น

ในคณิตศาสตร์สาขาทฤษฎีกราฟ ระดับขั้น (degree) ของ จุดยอด v ใน กราฟ เป็นจำนวนของ เส้นเชื่อม ซึ่งต่อกับจุดยอด v (สำหรับเส้นเชื่อมที่เป็นห่วง ให้นับ 2 ครั้ง) ดีกรีของจุดยอด $v$ เขียนแทนในทางคณิตศาสตร์ว่า $\deg(v).$ ดีกรีสูงสุดของกราฟ G เขียนแทนด้วย Δ(G) และดีกรีต่ำสุดของกราฟเขียนแทนด้วย δ(G)

กราฟไม่ระบุทิศทาง

กราฟที่มีจุดยอด 6 จุด และเส้นเชื่อม 7 เส้น

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

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

จุดยอด	ระดับขั้น
1	2
2	3
3	2
4	3
5	3
6	1

กราฟระบุทิศทาง

กราฟระบุทิศทางที่มีจุดยอด 4 จุด และเส้นเชื่อม 5 เส้น

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

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

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

จุดยอด	ระดับขั้นเข้า	ระดับขั้นออก
1	0	2
2	2	0
3	2	2
4	1	1

กรณีพิเศษ

กราฟไม่ระบุทิศทาง มีจุดยอด 4, 5, 6, 7, 10, 11, 12 เป็นใบ

จุดเอกเทศ

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

ใบ

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

กราฟปรกติ

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

แหล่งต้นทาง

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

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

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

ทฤษฎีการจับมือ

บทความหลัก: ทฤษฎีการจับมือ

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

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

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