ดูต้นฉบับสำหรับ บทตั้งการจับมือ

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

'''สูตรผลรวมระดับขั้น''' เป็นสูตรที่เป็นพื้นฐานของบทตั้งการจับมือ กล่าวไว้ว่า
: <math>\sum_{v\in V} \deg (v) = 2|E|</math>
สำหรับกราฟที่มี[[จุดยอด (ทฤษฎีกราฟ)|เซตจุดยอด]] ''V'' และ[[เส้นเชื่อม (ทฤษฎีกราฟ)|เซตเส้นเชื่อม]] ''E'' หรือก็คือ ผลรวมของระดับขั้นของจุดยอดทั้งหมด จะเท่ากับจำนวนสองเท่าของจำนวนเส้นเชื่อม [[เลออนฮาร์ด ออยเลอร์]]ได้พิสูจน์ว่าทั้ง''บทตั้งการจับมือ''และ''สูตรผลรวมระดับขั้น''เป็นจริงใน พ.ศ. 2279 ภายในผลงานเกี่ยวกับ[[สะพานทั้งเจ็ดแห่งเมืองเคอนิกส์แบร์ก]]ซึ่งเป็นจุดเริ่มต้นของ[[ทฤษฎีกราฟ]]นั่นเอง

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

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

[[หมวดหมู่:ทฤษฎีกราฟ]]