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