ดีกรีของจุดยอด

บทนิยาม ดีกรี (Degree) ของจุดยอด v ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด

ตัวอย่างของจำนวนดีกรี

จะเห็นว่า เส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่ เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่ เส้นเชื่อม ba, bc และ bb เป็นวงวน เกิดกับจุดยอด b กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้น โดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วง วงวนเป็น 2 ดังนั้น

ทฤษฎีบท 1       

ผลรวมของดีกรีของจุดยอดทุดจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ

จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4บทนิยาม ดีกรี (Degree) ของจุดยอด V ในกราฟ คือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v

พิสูจน์ เนื่องจากเส้นเชื่อมแต่ละเส้นในกราฟเกิดกับจุดยอดเป็นจำนวน 2 ครั้ง ดังนั้นจะนับเส้นเชื่อมแต่ละเส้น 2 ครั้งในผลรวมของดีกรีของจุดยอดทุกจุด 

นั่นคือ ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ 

 บทนิยาม

       จุดยอดที่มีดีกรีเป็นจำนวนคู่ เรียกว่า จุดยอดคู่ (Even Vertex)

       จุดยอดที่มีดีกรีเป็นจำนวนคี่ เรียกว่า จุดยอดคี่ (Odd Vertex)

จากรูปจะได้ว่า deg a = 2

                        deg b = 1

                        deg c = 3

                        deg d = 4

ดังนั้น จุดยอด a,d เป็นจุดยอดคู่

        จุดยอด b,c เป็นจุดยอดคี่

ทฤษฎีบท 2 

ทุกกราฟจะมีจุดยอดคี่เป็นจำนวนคู่

 

พิสูจน์ ให้ G เป็นกราฟ ถ้า G ไม่มีจุดยอดคี่ นั่นคือ G มีจำนวนจุดยอดคี่เป็นศูนย์

            จึงได้ว่าG มีจำนวนจุดยอดคี่เป็นจำนวนคู่

             ต่อไปสมมติว่า กราฟ G มีจุดยอดคี่ k จุด คือ v1, v2, v3, …, vk

            และมีจุดยอดคู่ n จุด คือ u1, u2, u3, …, un จากทฤษฎีบท 1 จะได้ว่า

            (deg v1 + deg v2 + … + deg vk) + (deg u1 + deg u2 + … + deg un) =2q

             เมื่อ q คือ จำนวนเส้นเชื่อมของ G

             ดังนั้น deg v1 + deg v2 + … + deg vk = 2q - (deg u1 + deg u2 + … + deg un)

             เนื่องจาก deg u1 + deg u2 + … + deg un ต่างก็เป็นจำนวนคู่

             ดังนั้น 2q - (deg u1 + deg u2 + … + deg un) เป็นจำนวนคู่

             นั่นคือ deg v1 + deg v2 + … + deg vk เป็นจำนวนคู่

             แต่เนื่องจาก deg v1 + deg v2 + … + deg vk เป็นจำนวนคี่

            เพราะฉะนั้น k จะต้องเป็นจำนวนคู่ จึงจะทำให้ deg v1 + deg v2 + … + deg vk เป็นจำนวนคู่ 

สรุปได้ว่า กราฟG มีจุดยอดคี่เป็นจำนวนคู่ จากตัวอย่าง เราให้เหตุผลโดยอาศัยทฤษฎีบท 2 ดังนี้ สมมติว่า มีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอด คือ 1,1, 2 และ 3 จะได้ว่า กราฟมีจุดยอดคี่เป็นจำนวน 3 จุด ซึ่งขัดแย้งกับทฤษฎีบท 2 สรุปได้ว่า ไม่มีกราฟที่มีสมบัติดังกล่าว