28 Feb
2007
28 Feb
'07
2:37 p.m.
Crossing number 1 -- Utility graph -- 6 vertices Crossing number 2 -- Petersen graph -- 10 vertices Crossing number 3 -- Heawood graph -- 14 vertices Crossing number 8 -- Mcgee graph -- 24 vertices. What are the simplest cubic graphs with crossing number 4-7 ? As a warm-up exercise to how tricky this problem is, show that a even n-gon with opposite corners connected has crossing number 1. (No need to post a proof here.) --Ed Pegg Jr