กราฟสองส่วนบริบูรณ์

ในคณิตศาสตร์สาขาทฤษฎีกราฟ กราฟสองส่วนบริบูรณ์ () คือ กราฟสองส่วนที่จุดยอดทุกจุดในเซตแรก เชื่อมโยงกับจุดยอดทุกจุดในเซตที่สอง

นิยาม 

กราฟสองส่วนบริบูรณ์  คือ กราฟสองส่วนที่ สำหรับจุดยอด  และ จุดยอด  จะมีเส้นเชื่อมเชื่อมระหว่าง  กับ  กราฟสองส่วนบริบูรณ์ที่มีขนาด  และ  จะเขียนแทนด้วย

ตัวอย่าง

คุณสมบัติ 

 กราฟเชิงระนาบ จะไม่มี  เป็นไมเนอร์
 กราฟสองส่วนบริบูรณ์  จะมีขนาดของการจับคู่สมบูรณ์เท่ากับ

ดูเพิ่ม 

 กราฟสองส่วน

ส