ต้นไม้ทุกต้นแยกเป็นสองฝ่าย. กราฟวัฏจักรที่มีจุดยอดเป็นจำนวนคู่จะเป็นแบบสองส่วน กราฟระนาบทุกกราฟที่มีใบหน้ายาวเท่ากันคือแบบสองส่วน
มีแผนภูมิสองส่วนทั้งหมดหรือไม่
ต้นไม้ทุกต้นแยกเป็นสองฝ่าย. กราฟวัฏจักรที่มีจุดยอดเป็นจำนวนคู่จะเป็นแบบสองส่วน กราฟระนาบทุกกราฟที่มีใบหน้ายาวเท่ากันคือแบบสองส่วน
ทำไมต้นไม้ทุกต้นถึงเป็นกราฟสองส่วน
ต้นไม้: ต้นไม้คือกราฟอย่างง่ายที่มีขอบ N – 1 โดยที่ N คือจำนวนของจุดยอด ซึ่งจะมีเส้นทางเดียวระหว่างจุดยอดสองจุดใดๆ สองฝ่าย: กราฟเป็นแบบสองส่วน ถ้าเราสามารถแบ่งจุดยอดออกเป็นสองชุดที่ไม่ปะติดปะต่อกัน V1, V2 โดยที่ขอบไม่มีจุดเชื่อมต่อจากชุดเดียวกัน
คุณจะพิสูจน์ได้อย่างไรว่าต้นไม้ทุกต้นเป็นกราฟสองส่วน
ให้ เป็นเซตของจุดยอดที่มีเครื่องหมาย '' และเป็นเซตของจุดยอดที่มี '' เห็นได้ชัดว่าจุดยอดที่แตกต่างกันสองจุดไม่ได้อยู่ติดกับขอบ และเช่นเดียวกันสำหรับ เนื่องจากต้นไม้ไม่มีวงจร นอกจากนี้ ให้แบ่งชุดจุดยอดของกราฟออกเป็นสองชุดย่อยที่ไม่ปะติดปะต่อกันอย่างชัดเจน ดังนั้น ต้นไม้ใด ๆ ที่เป็นสองฝ่าย
ทุก ๆ กราฟสมบูรณ์ bipartite?
ทุกกราฟคู่ที่สมบูรณ์ ก , เป็นกราฟของ Moore และ a (n, 4)-cage กราฟสองส่วนที่สมบูรณ์ K , และ K , +1 มีจำนวนขอบสูงสุดที่เป็นไปได้ในกราฟที่ไม่มีรูปสามเหลี่ยมทั้งหมดที่มีจุดยอดเท่ากัน นี่คือทฤษฎีบทของหิ้ง