คำถามทฤษฎีกราฟพิสูจน์

Aug 16 2020

ฉันไม่สามารถหาหลักฐานเกี่ยวกับข้อความนี้ได้ -

พิจารณา G เป็นกราฟระนาบที่เชื่อมต่อกัน ถ้า G ไม่ใช่สองฝ่ายการฝังระนาบของ G จะมีอย่างน้อย 2 ใบหน้าที่มีองศาคี่

มีใครช่วยพิสูจน์ได้ไหม

คำตอบ

4 PrabhSimranSinghBadwal Aug 16 2020 at 18:43

เนื่องจาก G ไม่ใช่ bipartite G จึงมีวัฏจักรคี่ C. $F_{1},F_{2},......,F_{k}$เป็นใบหน้าด้านใน C ในการฝังระนาบ พิจารณาผลรวมขององศาของใบหน้าเหล่านี้

  • แต่ละขอบใน C จะถูกนับหนึ่งครั้ง
  • ให้ D เป็นเซตของขอบบนขอบเขตใด ๆ $F_{i}$แต่ไม่ใช่ใน C.

แต่ละขอบใน D จะถูกนับสองครั้ง

ดังนั้น $\sum_{i}$ $\deg(F_{i})$ = $|E(C)| + 2|D|$

ตั้งแต่ $|E(C)|$ เป็นเลขคี่และ $2|D|$ เป็นคู่

$\sum_{i}$ $\deg(F_{i})$ เป็นเรื่องแปลกดังนั้น $\deg(F_{i})$ ต้องแปลกสำหรับบางคน $i$

ดังนั้นอย่างน้อยหนึ่งหน้าใน C จึงมีองศาคี่

สามารถใช้อาร์กิวเมนต์เดียวกันเพื่อแสดงว่าอย่างน้อยหนึ่งครั้งที่ใบหน้าภายนอก C มีองศาคี่