กำลังเตรียมมุกหลอกเด็ก ๆ เรื่องกราฟ ปัญหาคลาสสิกส่วนใหญ่เอามาจากเล่มนี้ฮะ พอลอกทฤษฎีบทหนึ่งที่ว่า "กราฟ G เป็น bipartite ก็ต่อเมื่อ G ไม่มี odd cycle" จากหนังสือลงสไลด์เสร็จ ก็อยากได้ตัวอย่างเก๋ ๆ ประกอบสักอัน ทำให้นึกถึง chess puzzle ข้อหนึ่งซึ่งเคยเล่นสมัยเด็ก ๆ
จากรูปกระดานหมากรุก ฝ่ายดำสามารถชนะได้มั้ย เราจะตอบคำถามนี้ได้ก็ต้องรู้ก่อนว่าตาต่อไปใครเดิน ถ้าตาต่อไปขาวเดิน ดำชนะได้ เพราะดำสามารถโปรโมตเบี้ย แต่ถ้าตาต่อไปดำเป็นฝ่ายเดินล่ะ ดำก็ต้องเดินม้า (เพราะเป็นตัวเดียวที่เดินได้) หลังจากดำเดินม้า ขาวที่เล่นเป็น เขาจะเดินไป c2 เพื่อกักคิงดำ (เพราะคิงดำขวางการโปรโมตเบี้ยของตัวเองอยู่) แล้วขาวจะพยายามเดินกลับไปกลับมาระหว่าง c1 และ c2 เพื่อไม่ให้เบี้ยถูกโปรโมต ถ้าขาวทำสำเร็จ ดำก็ไม่ชนะ
คำถามคือ ม้าดำสามารถเดินด้วยเส้นทางไหนก็ตามแต่เพื่อยับยั้งไม่ให้คิงขาวเดินกลับไปกลับมาระหว่าง c1 กับ c2 ได้มั้ย (พูดอีกอย่างว่า [กรณี ก.] ถ้า ณ เวลาหนึ่ง คิงขาวอยู่ c1 และดำเป็นฝ่ายได้เดิน ม้าดำต้องเดินไปยังตำแหน่งใดตำแหน่งหนึ่งต่อไปนี้ a3, b4, d4, e3 หรือ e1 เพราะตำแหน่งเหล่านั้นจะยับยั้งไม่ให้คิงขาวเดินไป c2 หรือ [กรณี ข.] ถ้า ณ เวลาหนึ่ง คิงขาวอยู่ c2 และดำเป็นฝ่ายได้เดิน ม้าดำต้องเดินหนึ่งทีไปยังตำแหน่งใดตำแหน่งหนึ่งต่อไปนี้ b3, d3 หรือ e2 เพราะตำแหน่งดังกล่าวจะยับยั้งไม่ให้คิงขาวเดินไป c1)
possible paths มีมากมายมหาศาล เราจะรู้ได้อย่างไรว่าในจำนวน paths มากมายนั้น ไม่มีสัก path เดียวที่ม้าดำจะสามารถยับยั้งการเดินกลับไปกลับมาของคิงขาวได้ คำตอบอยู่ที่ bipartite graph ไม่มี odd cycle ฮะ
มองกระดานหมากรุกเป็นกราฟ G โดยให้ช่องกระดานทั้ง 64 ช่องเป็น vertices และ vertices สองตัวใด ๆ มี edge เชื่อมกันถ้าม้าสามารถเดินถึงกันได้ใน 1 ที เนื่องจากรูปแบบการเดินม้า 1 ทีบังคับให้มันต้องเปลี่ยนสีของช่องกระดานหมากรุก ฉะนั้น G เป็น bipartite (เซ็ตของ vertices เซ็ตหนึ่งคือเซ็ตของช่องสีดำ และอีกเซ็ตหนึ่งคือช่องสีขาว) บางครั้งเราก็ตั้งชื่อให้ G ว่า Knight's graph
จากรูปโจทย์ ถ้าฝ่ายสีดำจะทำให้เป็นกรณี ก. ม้าดำต้องเดินจำนวนคี่ทีจากช่องสีดำที่มันอยู่เพื่อให้ไปลงในช่อง a3, b4, d4, e3 หรือ e1 ซึ่งเป็นช่องสีดำเหมือนกัน จึงเห็นว่ากรณีนี้เป็นไปไม่ได้เพราะ bipartite graph ไม่มี cycle คี่ (กรณี ข. ก็ทำนองเดียวกัน)