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

ดังนั้น เป็นไปไม่ได้ที่จะมีกราฟดังกล่าว

                          deg b   =   3

deg c   =   0

deg d   =   3

deg e   =   2

ดังนั้น          จุดยอด a, c และ e เป็นจุดยอดคู่

    จุดยอด b และ d เป็นจุดยอดคี่

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

พิสูจน์   ให้ G เป็นกราฟ

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

G มีจำนวนจุดยอดคี่เป็นจำนวนคู่

ต่อไปสมมุติว่ากราฟ G มีจุดยอดที่ k จุด คือ V₁, V₂, V₃,…,V_k

และมีจุดยอดคู่ n จุด คือ u₁, u₂, u₃, …, u_n จากทฤษฎีบท 1 จะได้ว่า

(deg v₁ + deg v₂ + … +deg v_k) + (deg u₁ + deg u₂  + … + deg u_n)  =  2q

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

ดังนั้น   deg v₁ + deg v₂ + … + deg v_k  = 2q  – (deg u₁ +deg u₂ + … + deg u_n)

เนื่องจาก   deg u₁,  deg u₂ , … , deg u_n   ต่างก็เป็นจำนวนคู่

ดังนั้น 2q – (deg  u₁  + deg u₂ + … +deg u_n)   เป็นจำนวนคู่

นั่นคือ dewg v₁ + deg v₂ + …deg v_k  เป็นจำนวนคู่

แต่เนื่องจาก deg v₁ , deg v₂ , … , deg v_k เป็นจำนวนคี่

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

เป็นจำนวนคู่ สรุปได้ว่า กราฟ 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 อำเภอมีถนนเชื่อมกับอำเภออื่นที่เหลือทุกอำเภอ