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

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

สูตรผลรวมระดับขั้น เป็นสูตรที่เป็นพื้นฐานของบทตั้งการจับมือ กล่าวไว้ว่า

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

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

การพิสูจน์

ออยเลอร์ได้พิสูจน์บทตั้งการจับมือโดยนับจำนวนของคู่ลำดับ (v, e) โดยที่ e แทนด้วยเส้นเชื่อม และ v แทนด้วยจุดยอดที่เป็นปลายของเส้นเชื่อมนั้น เนื่องจากเส้นเชื่อมมีปลายสองด้านจึงนับรวมได้ทั้งหมด 2|E| นอกจากนี้ ระดับชั้นของจุดยอดก็คือจำนวนของเส้นเชื่อมที่มีปลายข้างหนึ่งที่จุดยอดนั้น ดังนั้นผลรวมของระดับขั้นก็คือจำนวนของคู่ลำดับ (v, e) ซึ่งก็คือ 2|E| ด้วย

นอกจากนี้ เนื่องจากระดับขั้นของจุดยอดเป็นจำนวนเต็ม และค่า 2|E| เป็นจำนวนเต็มคู่ หากมีจุดยอดที่มีระดับขั้นคี่เป็นจำนวนคี่จะทำให้สมการไม่เป็นจริงเนื่องจากด้านซ้ายสมการเป็นจำนวนเต็มคี่ ส่วนด้านขวาสมการเป็นจำนวนเต็มคู่ ดังนั้นจึงได้ว่าจุดยอดที่มีระดับขั้น คี่จะมีเป็นจำนวนคู่เสมอ