Kuratowski's theorem

[calfever]

จากทฤษฎีที่บอกว่า กราฟจะเปนplanarก็ต่อเมื่อกราฟนั้นมีสับกราฟซึ่งhomeomorphicกับK3,3หรือK5

อยากทราบว่า มีวิธีการดูอย่างไรว่าจะเลือกกราฟK3,3หรือK5มาพิจารณา?

ขอถามอีกข้อเลยละกัน--"
เค้าให้พิสูจน์ว่าCycle graph Cn is isomorphic to K3 for n>=1.
โดยกำหนดให้เลือกใช้C7. พอเอามาวาดดูแล้วไม่เห็นจะisomorphicกันเลยอ่ะค่ะ งงๆ
หรือให้ตอบว่าบทพิสูจน์นี้ไม่เป็นความจริง

[picmy]

ข้อความเดิมเขียนโดยคุณ calfever

จากทฤษฎีที่บอกว่า กราฟจะเปนplanarก็ต่อเมื่อกราฟนั้นมีสับกราฟซึ่งhomeomorphicกับK3,3หรือK5

ผมขอเติมนิดนึงนะครับว่า ในที่นี้น่าจะตกคำว่า "ไม่"ไปตัวนึง
ตัวทฤษฎีบทจริงๆแล้วบอกว่า

"กราฟจะเป็นplanarก็ต่อเมื่อกราฟนั้นไม่่มีสับกราฟซึ่งhomeomorphicกับK3,3หรือK5"
ส่วนเรื่องการนำเอาทฤษฎีบทนี้มาใช้ มักจะใช้ในการพิสูจน์ว่ากราฟๆนึงไม่ใช่ planar โดยต้องพยายามหาสับกราฟของกราฟนั้นที่homeomorphicกับK3,3หรือK5 (อย่าถามผมว่าหายังไงนะครับ อันนี้คงต้องพึ่งประสบการณ์ครับ) ถ้าหาเจอ ก็แสดงว่ากราฟนั้นไม่ใช่ planar กราฟ
แต่ถ้าหาไม่เจอ ต้องแน่ใจว่าพิจารณาในทุกสับกราฟแล้ว(ซึ่งถ้า กราฟนั้นมีจำนวนจุดมากๆ แล้วหละก็ คงต้องเหนื่อยหน่อยนะครับ) ถึงจะสรุปได้ว่า กราฟนั้นเป็น planar
ดังนั้นในการที่จะแสดงว่ากราฟๆนึงเป็น planar นั้นมักจะไม่ใช้วิธีดังกล่าวข้างต้น(ไม่เสมอไป แต่มักจะไม่ใช้) แต่เราใช้วิธีพยายามแสดงให้ได้ว่ากราฟที่เราต้องการจะพิสูจนนั้น์ homeomorphic กับ planar กราฟที่เรารู้จัก (อันนี้ก็ต้องใช้ประสบการณ์ครับ)
ถ้า $n>3$ แล้ว $C_n$ ไม่ isomorphic กับ $K_3$ แต่ homeomorphic กับ $K_3$