From what I know, this should not be a planar graph because it contains a subgraph homeomorphic ot K3,3. With (g,h) and (c,d) as the pairs. Correct me if I am wrong.
-ngw

==

Actually, two sets of vertices should be {a,e,g} and {b,f,h}. It's K_3,3 after all :). --Asuleime 19:24, 1 December 2008 (UTC)

You're right, it's homeomorphic to K_3,3 so we just use Theorem 2 to prove it's not planar. --Tsnowdon 01:26, 4 December 2008 (UTC)