ในทฤษฎีกราฟทฤษฎีกราฟสมบูรณ์แบบที่แข็งแกร่งเป็นการกำหนดลักษณะกราฟที่ต้องห้ามของกราฟสมบูรณ์แบบว่าเป็นกราฟที่ไม่มีทั้งรูคี่ ( วงจรเหนี่ยวนำ ความยาวคี่ ที่มีความยาวอย่างน้อย 5) และแอนติรูคี่ (ส่วนเติมเต็มของรูคี่) Claude Berge ตั้งข้อสันนิษฐานนี้ในปี1961 Maria Chudnovsky , Neil Robertson , Paul SeymourและRobin Thomasประกาศการพิสูจน์ในปี 2002 ^{[ 1 ]}และตีพิมพ์โดยพวกเขาในปี 2006

การพิสูจน์ทฤษฎีบทกราฟที่สมบูรณ์แบบที่แข็งแกร่งทำให้ผู้เขียนได้รับรางวัลมูลค่า 10,000 ดอลลาร์จากGérard Cornuéjolsแห่งมหาวิทยาลัย Carnegie Mellon ^{[ 2 ]}และรางวัล Fulkersonประจำ ปี 2009 ^{[ 3 ]}

กราฟสมบูรณ์ (Perfect graph ) คือกราฟที่สำหรับทุกกราฟย่อยเหนี่ยวนำ (induced subgraph ) ขนาดของกลุ่มคลิกสูงสุด (maximum clique)จะเท่ากับจำนวนสีขั้นต่ำในการระบายสีกราฟนั้น กราฟสมบูรณ์รวมถึงกราฟหลายประเภทที่รู้จักกันดี เช่นกราฟสองส่วน (bipartite graphs) กราฟคอร์ดัล ( chordal graphs ) และกราฟเปรียบเทียบ (comparability graphs ) ในงานเขียนปี 1961 และ 1963 ของ Claude Bergeที่กำหนดนิยามของกราฟประเภทนี้เป็นครั้งแรกเขาพบว่ากราฟสมบูรณ์ไม่สามารถมีรูคี่ (odd hole) ซึ่งเป็นกราฟย่อยเหนี่ยวนำในรูปแบบของกราฟวงจร ความยาว คี่ที่มีความยาวห้าหรือมากกว่านั้นได้ เพราะรูคี่มีจำนวนกลุ่มคลิกสองและจำนวนสีสาม ในทำนองเดียวกัน เขาพบว่ากราฟสมบูรณ์ไม่สามารถมีแอนติโฮลคี่ (odd antiholes) ซึ่งเป็นกราฟย่อยเหนี่ยวนำที่เสริมกับรูคี่ได้ แอนติโฮลคี่ที่มี 2k +  1 จุดยอดจะมีจำนวนกลุ่มคลิกkและจำนวนสีk  + 1 ซึ่งเป็นไปไม่ได้สำหรับกราฟสมบูรณ์ กราฟที่ไม่มีทั้งรูคี่และแอนติโฮลคี่จึงเป็นที่รู้จักในชื่อกราฟ Berge

เบอร์เกอตั้งข้อสันนิษฐานว่ากราฟเบอร์เกอทุกกราฟเป็นกราฟสมบูรณ์ หรือกล่าวอีกนัยหนึ่งคือ กราฟสมบูรณ์และกราฟเบอร์เกอต่างก็กำหนดกลุ่มของกราฟเดียวกัน ข้อสันนิษฐานนี้เป็นที่รู้จักกันในชื่อข้อสันนิษฐานกราฟสมบูรณ์ที่แข็งแกร่ง จนกระทั่งได้รับการพิสูจน์ในปี 2002 จึงเปลี่ยนชื่อเป็นทฤษฎีบทกราฟสมบูรณ์ที่แข็งแกร่ง

ข้อสันนิษฐานอีกประการหนึ่งของเบอร์เก ซึ่งได้รับการพิสูจน์ในปี 1972 โดยลาซโล โลวัสซ์ คือ ส่วนเติมเต็มของกราฟสมบูรณ์ทุกกราฟก็เป็นกราฟสมบูรณ์เช่นกัน สิ่งนี้เป็นที่รู้จักกันในชื่อทฤษฎีบทกราฟสมบูรณ์หรือ (เพื่อแยกแยะออกจากข้อสันนิษฐาน/ทฤษฎีบทกราฟสมบูรณ์ที่เข้มงวด) ทฤษฎีบทกราฟสมบูรณ์แบบอ่อน เนื่องจากลักษณะเฉพาะของกราฟต้องห้ามของเบอร์เกนั้นเป็นส่วนเติมเต็มในตัวเอง ทฤษฎีบทกราฟสมบูรณ์แบบอ่อนจึงได้มาโดยตรงจากทฤษฎีบทกราฟสมบูรณ์ที่เข้มงวด

การพิสูจน์ทฤษฎีบทกราฟสมบูรณ์แบบที่แข็งแกร่งโดย Chudnovsky และคณะ เป็นไปตามโครงร่างที่คาดการณ์ไว้ในปี 2001 โดย Conforti, Cornuéjols, Robertson, Seymour และ Thomas ซึ่งระบุว่ากราฟ Berge ทุกกราฟจะประกอบด้วยหน่วยสร้างพื้นฐาน 5 ประเภท (คลาสพิเศษของกราฟสมบูรณ์แบบ) หรือมีการแยกโครงสร้างออกเป็นกราฟที่เรียบง่ายกว่า 4 ประเภท กราฟ Berge ที่ไม่สมบูรณ์แบบขั้นต่ำไม่สามารถมีการแยกโครงสร้างเหล่านี้ได้ ซึ่งส่งผลให้ไม่มีตัวอย่างค้านสำหรับทฤษฎีบทนี้^{[ 4 ]}แนวคิดนี้อิงจากการแยกโครงสร้างที่คาดการณ์ไว้ก่อนหน้านี้ในลักษณะเดียวกัน ซึ่งจะบ่งชี้ถึงข้อสันนิษฐานกราฟสมบูรณ์แบบที่แข็งแกร่ง แต่กลับกลายเป็นเท็จ^{[ 5 ]}

กราฟสมบูรณ์แบบพื้นฐานห้าประเภทที่ประกอบเป็นกรณีพื้นฐานของการแยกโครงสร้างนี้ ได้แก่ กราฟสองส่วนกราฟเส้นของกราฟสองส่วนกราฟส่วนเติมเต็มของกราฟสองส่วน ส่วนเติมเต็มของกราฟเส้นของกราฟสองส่วน และกราฟแยกสองชั้น เห็นได้ชัดว่ากราฟสองส่วนเป็นกราฟสมบูรณ์แบบ: ในกราฟย่อยเหนี่ยวนำที่ไม่ใช่กราฟย่อยศูนย์ จำนวนคลิกและจำนวนสีมีค่าเท่ากับสองทั้งคู่ ดังนั้นจึงเท่ากัน ความสมบูรณ์แบบของส่วนเติมเต็มของกราฟสองส่วน และของส่วนเติมเต็มของกราฟเส้นของกราฟสองส่วน เทียบเท่ากับทฤษฎีบทของ Kőnigที่เชื่อมโยงขนาดของการจับคู่สูงสุดเซตอิสระสูงสุดและการปกคลุมจุดยอดขั้นต่ำในกราฟสองส่วน ความสมบูรณ์แบบของกราฟเส้นของกราฟสองส่วนสามารถกล่าวได้เทียบเท่ากับข้อเท็จจริงที่ว่ากราฟสองส่วนมีดัชนีสีเท่ากับดีกรี สูงสุด ซึ่งพิสูจน์โดยKőnig (1916)ดังนั้น กราฟพื้นฐานทั้งสี่ประเภทนี้จึงเป็นกราฟสมบูรณ์แบบ กราฟแยกคู่เป็นกราฟแยก ประเภท ที่สามารถแสดงให้เห็นว่าสมบูรณ์แบบได้เช่นกัน^{[ 6 ]}

การแยกส่วนสี่ประเภทที่พิจารณาในบทพิสูจน์นี้ ได้แก่ 2-joins, complements of 2-joins, balanced skew partitions และ homogeneous pairs

2-join คือการแบ่งจุดยอดของกราฟออกเป็นสองเซตย่อย โดยมีคุณสมบัติว่าขอบที่เชื่อมระหว่างเซตย่อยทั้งสองนี้จะสร้างกราฟสองส่วนสมบูรณ์ ที่ไม่ทับซ้อนกันสอง กราฟ เมื่อกราฟมี 2-join แล้ว กราฟนั้นสามารถแยกย่อยออกเป็นกราฟย่อยแบบเหนี่ยวนำที่เรียกว่า "บล็อก" ได้ โดยการแทนที่เซตย่อยของจุดยอดเซตหนึ่งด้วยเส้นทางที่สั้นที่สุดภายในเซตย่อยนั้น ซึ่งเชื่อมต่อกราฟสองส่วนสมบูรณ์กราฟหนึ่งกับอีกกราฟหนึ่ง หากไม่มีเส้นทางดังกล่าว บล็อกจะถูกสร้างขึ้นโดยการแทนที่เซตย่อยของจุดยอดเซตหนึ่งด้วยจุดยอดสองจุด จุดละหนึ่งจุดสำหรับกราฟสองส่วนสมบูรณ์แต่ละกราฟ 2-join จะสมบูรณ์ก็ต่อเมื่อบล็อกทั้งสองของมันสมบูรณ์ ดังนั้น หากกราฟที่ไม่สมบูรณ์อย่างน้อยที่สุดมี 2-join มันจะต้องเท่ากับบล็อกใดบล็อกหนึ่ง ซึ่งหมายความว่ามันจะต้องเป็นวัฏจักรคี่และไม่ใช่ Berge ด้วยเหตุผลเดียวกัน กราฟที่ไม่สมบูรณ์ขั้นต่ำซึ่งส่วนเติมเต็มมีการเชื่อมต่อ 2-join ไม่สามารถเป็น Berge ได้^{[ 7 ]}

การแบ่งส่วนแบบเฉียง (skew partition ) คือการแบ่งจุดยอดของกราฟออกเป็นสองเซตย่อย โดยเซตหนึ่งก่อให้เกิดกราฟย่อยที่ไม่เชื่อมต่อกัน และอีกเซตหนึ่งมีส่วนเติมเต็มที่ไม่เชื่อมต่อกันChvátal (1985)ได้ตั้งข้อสันนิษฐานว่าไม่มีตัวอย่างค้านขั้นต่ำสุดสำหรับทฤษฎีบทกราฟสมบูรณ์แบบที่แข็งแกร่งที่จะมีการแบ่งส่วนแบบเฉียงได้ Chudnovsky และคณะได้แนะนำข้อจำกัดทางเทคนิคบางประการเกี่ยวกับการแบ่งส่วนแบบเฉียง และสามารถแสดงให้เห็นว่าข้อสันนิษฐานของ Chvátal เป็นจริงสำหรับ "การแบ่งส่วนแบบเฉียงที่สมดุล" ที่ได้ ข้อสันนิษฐานทั้งหมดเป็นผลลัพธ์ของทฤษฎีบทกราฟสมบูรณ์แบบที่แข็งแกร่ง^{[ 8 ]}

คู่โฮโมจีนัสเกี่ยวข้องกับการแยกส่วนแบบโมดูลาร์ของกราฟ มันคือการแบ่งกราฟออกเป็นสามเซตย่อยV ₁ , V ₂และV ₃โดยที่V ₁และV ₂รวมกันมีจุดยอดอย่างน้อยสามจุดV ₃มีจุดยอดอย่างน้อยสองจุด และสำหรับแต่ละจุดยอดvใน V ₃และแต่ละiใน {1,2} vจะอยู่ติดกับจุดยอดทั้งหมดในV _iหรือไม่ติดกับจุดยอดใดเลย กราฟที่ไม่สมบูรณ์ขั้นต่ำไม่สามารถมีคู่โฮโมจีนัสได้^{[ 9 ]}หลังจากการพิสูจน์สมมติฐานกราฟที่สมบูรณ์แบบอย่างเข้มแข็งChudnovsky (2006)ได้ทำให้ง่ายขึ้นโดยแสดงให้เห็นว่าคู่โฮโมจีนัสสามารถถูกกำจัดออกจากเซตของการแยกส่วนที่ใช้ในการพิสูจน์ได้

การพิสูจน์ว่ากราฟ Berge ทุกกราฟจะตกอยู่ในหนึ่งในห้าคลาสพื้นฐานหรือมีการแยกส่วนหนึ่งในสี่ประเภทนั้น เป็นไปตามการวิเคราะห์กรณี โดยพิจารณาจากว่ามีการกำหนดค่าบางอย่างอยู่ในกราฟหรือไม่ ได้แก่ "stretcher" ซึ่งเป็นกราฟย่อยที่สามารถแยกส่วนออกเป็นเส้นทางเหนี่ยวนำสามเส้นทางภายใต้ข้อจำกัดเพิ่มเติมบางประการ ส่วนเติมเต็มของ stretcher และ "proper wheel" ซึ่งเป็นการกำหนดค่าที่เกี่ยวข้องกับกราฟ wheelประกอบด้วยวงจรเหนี่ยวนำพร้อมกับจุดยอดฮับที่อยู่ติดกับจุดยอดวงจรอย่างน้อยสามจุดและเป็นไปตามข้อจำกัดเพิ่มเติมหลายประการ สำหรับแต่ละตัวเลือกที่เป็นไปได้ว่ามี stretcher หรือส่วนเติมเต็มหรือ proper wheel อยู่ในกราฟ Berge ที่กำหนดหรือไม่ กราฟนั้นสามารถแสดงได้ว่าอยู่ในหนึ่งในคลาสพื้นฐานหรือสามารถแยกส่วนได้^{[ 10 ]}การวิเคราะห์กรณีนี้ทำให้การพิสูจน์เสร็จสมบูรณ์

• ทฤษฎีบทกราฟที่สมบูรณ์แบบที่แข็งแกร่ง , Václav Chvátal
• ไวส์สไตน์, เอริค ดับเบิลยู. "ทฤษฎีบทกราฟสมบูรณ์แบบที่แข็งแกร่ง" . MathWorld .