พิจารณากราฟต่อไปนี้
จะเห็นว่าเส้นเชื่อมที่เกิดกับจุดยอด a ได้แก่เส้นเชื่อม ab และ ac ดังนั้น จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด a คือ 2 สำหรับจุดยอด b มีเส้นเชื่อมที่เกิดกับจุดยอด b ได้แก่เส้นเชื่อม ba, bc และ bb เส้นเชื่อม bb เป็นวงวน เกิดกับจุดยอด b กรณีที่มีเส้นเชื่อมเป็นวงวนจะกำหนดให้นับจำนวนเส้นเชื่อมที่เกิดกับจุดยอดนั้นเพิ่มขึ้นโดยให้นับเส้นเชื่อมที่เป็นวงวน 1 วงวนเป็น 2 ดังนั้นจำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด b จึงเป็น 4 สรุปเป็นตารางได้ดังนี้
บทนิยาม
ดีกรี (degree) ของจุดยอด v ในกราฟคือ จำนวนครั้งทั้งหมดที่เส้นเชื่อมเกิดกับจุดยอด v
ใช้สัญลักษณ์ deg v แทนดีกรีของจุดยอด v
ตัวอย่างที่ 1 กำหนดกราฟ ดังรูป
จากรูปจะได้ว่า deg a = 2
deg b = 1
deg c = 3
deg d = 4
ตัวอย่างที่ 1 กำหนดกราฟ ดังรูป
จากรูปจะได้ว่า deg a = 2
deg b = 5
deg c = 5
deg d = 4
สังเกตว่า deg a + deg b + deg c + deg d = 16
และกราฟมีจำนวนเส้นเชื่อมทั้งหมด 8 เส้น
ความสัมพันธ์ระหว่างผลรวมของดีกรีของจุดยอดทุกจุดในกราฟกับจำนวนเส้นเชื่อมของกราฟเป็นไปตามทฤษฎีบทต่อไปนี้
ทฤษฎีบท 1
ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ
พิสูจน์
เนื่องจากเส้นเชื่อมแต่ละเส้นในกราฟเกิดกับจุดยอดเป็นจำนวน 2 ครั้ง ดังนั้นเส้นเชื่อมแต่ละเส้นจะถูกนับ 2 ครั้งในผลรวมของดีกรีของจุดยอดทุกจุด
นั่นคือ ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับสองเท่าของจำนวนเส้นเชื่อมในกราฟ
ข้อสังเกต
ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเป็นจำนวนคู่เสมอ
ตัวอย่างที่ 2 จงหาจำนวนเส้นเชื่อมของกราฟที่มีผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับ 22
วิธีทำ สมมุติว่ากราฟมีเส้นเชื่อม n เส้น
จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับ
สองเท่าของจำนวนเส้นเชื่อมในกราฟ
ดังนั้น 22 = 2n
นั่นคือ n = 11
สรุปได้ว่า กราฟมีเส้นเชื่อม 11 เส้น
ตัวอย่างที่ 3 จงหาจำนวนจุดยอดของกราฟที่มีเส้นเชื่อม 15 เส้น และมีจุดยอด 3 จุด ที่มีดีกรี 4 ส่วนจุดยอดที่เหลือทีดีกรี 3
วิธีทำ ให้ n เป็นจำนวนจุดยอดที่มีดีกรี 3
ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟคือ (3)(4) + 3n
จากทฤษฎีบท 1 ผลรวมของดีกรีของจุดยอดทุกจุดในกราฟเท่ากับ
สองเท่าของจำนวนเส้นเชื่อมในกราฟ
ดังนั้น (3)(4) +3n = 2(15)
เพราะฉะนั้น n = 6
ดังนั้น จำนวนจุดยอดทั้งหมดของกราฟคือ 3+6 = 9 จุด
ตัวอย่างที่ 4 จงพิจารณาว่าเป็นไปได้หรือไม่ว่าจะมีกราฟที่มีจุดยอด 4 จุด และ ดีกรีของจุกยอดคือ 1, 1, 2 และ 3 ตามลำดับ
วิธีทำ สมมุติว่ามีกราฟที่มีจุดยอด 4 จุด และดีกรีของจุดยอดเท่ากับ 1, 1, 2 และ 3
ดังนั้น ผลรวมของดีกรีของจุดยอดทุกจุดคือ 1 + 1 + 2 + 3 = 7
ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท 1
ดังนั้น เป็นไปไม่ได้ที่จะมีกราฟดังกล่าว
บทนิยาม
จุดยอดที่มีดีกรีเป็นจำนวนคู่ เรียกว่า จุดยอดคู่ (even vertex)
จุดยอดที่มีดีกรีเป็นจำนวนคี่ เรียกว่า จุดยอดคี่ (odd vertex)
ตัวอย่างที่ 5 กำหนดกราฟ ดังรูป
จากรูป deg a = 2
deg b = 3
deg c = 0
deg d = 3
deg e = 2
ดังนั้น จุดยอด a, c และ e เป็นจุดยอดคู่
จุดยอด b และ d เป็นจุดยอดคี่
ทฤษฎีบท 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) เป็นจำนวนคู่
นั่นคือ dewg v1 + deg v2 + …deg vk เป็นจำนวนคู่
แต่เนื่องจาก deg v1 , deg v2 , … , deg vk เป็นจำนวนคี่
เพราะฉะนั้น k จะต้องเป็นจำนวนคู่ จึงจะทำให้ deg v1 + deg v2 + … + deg vk
เป็นจำนวนคู่ สรุปได้ว่า กราฟ G มีจุดยอดคี่เป็นจำนวนคู่ #
จากตัวอย่างมีกราฟที่มีจุดยอด 4 จุดและดีกรีของจุดยอดคือ 1, 1, 2 และ 3
จะได้ว่ากราฟมีจุดยอดคี่เป็นจำนวน 3 จุด ซึ่งขัดแย้งกับทฤษฎีบท 2
สรุปได้ว่าไม่มีกราฟที่มีสมบัติดังกล่าว
ตัวอย่างที่ 6 ถ้าในห้องประชุมแห่งหนึ่งมีผู้เข้าประชุมทั้งหมด 23 คน เป็นไปได้หรือไม่ว่าผู้เข้าร่วมประชุมแต่ละคนจับมือทักทายของผู้เข้าร่วมประชุมคนอื่นเพียง 7 คนเท่านั้น
วิธีทำ แปลงปัญหาดังกล่าวเป็นกราฟ โดยให้จุดยอดแทนผู้เข้าร่วมประชุม และ
เส้นเชื่อมแทนการจับมือทักทายของผู้เข้าร่วมประชุม
จะได้ว่า กราฟนี้มีจุดยอด 23 จุด และจุดยอดแต่ละจุดมีดีกรี 7
นั่นคือ กราฟมีจุดยอดคี่เป็นจำนวน 23 จุด ซึ่งเป็นจำนวนคี่ ขัดแย้ง
กับทฤษฎีบท 2 ดังนั้น เป็นไปไม่ได้ที่ผู้เข้าร่วมประชุมแต่ละคนจับมือกับคนอื่นเพียง 7 คนเท่านั้น
ตัวอย่างที่ 7 จงพิจารณาว่าเป็นไปได้หรือไม่ที่จังหวัดหนึ่งซึ่งมี 5 อำเภอ โดยมี 3 อำเภอซึ่งแต่ละอำเภอมีถนนเชื่อมกับอำเภออื่นเพียง 3 สาย มี 1 อำเภอ ที่มีถนนเชื่อมกับอำเภออื่นเพียง 2 สาย และมี 1 อำเภอมีถนนเชื่อมกับอำเภออื่นที่เหลือทุกอำเภอ
วิธีทำ แปลงปัญหาดังกล่าวเป็นกราฟ โดยให้จุดยอดแทนอำเภอ และ
เส้นเชื่อมแทนถนนที่เชื่อมระหว่างสองอำเภอใดๆ
นั่นคือ กราฟนี้มีจุดยอด 5 จุด และมีดีกรี 3, 3, 3, 2, 4 จะได้ว่า
กราฟมีจุดยอดคี่เป็นจำนวน 3 จุด ซึ่งเป็นจำนวนคี่ ขัดแย้งกับทฤษฎีบท2
ดังนั้นเป็นไปไม่ได้ที่จังหวัดหนึ่งที่มี 5 อำเภอ จะมี 3 อำเภอ ซึ่งแต่ละอำเภอ
มีถนนเชื่อมกับอำเภออื่นเพียง 3 สาย มี 1 อำเภอ ที่มีถนนเชื่อมกับอำเภอ
อื่นเพียง 2 สาย และมี 1 อำเภอมีถนนเชื่อมกับอำเภออื่นที่เหลือทุกอำเภอ
