I need to construct a graph that cannot be embedded in the surface of a torus and an outline for this claim.?

Question

How do I do this? I have been stuck on this for days.

This is for a graph theory class I'm taking. Please if anyone can help that's great! I have been stuck on this for days.

Answer 1

What I'd do is construct a graph that has only one essential way of being embedded in a torus, and then add in some extra edges.

Try this. Take the four points (1,0,0), (1,0,1), (1,0,2), (2,0,2). They form a square, with two sides each parallel to the x and z axes. Connect adjacent vertices. Rotate the whole thing 90 degrees around the z axis. Connect corresponding vertices. Repeat. Repeat again. Repeat one more time (recreating the original square).

You now have a graph with 16 vertices that has a really obvious embedding in a torus -- but only one, up to homotopy.

Add in one more edge, directly connecting vertices on opposite sides of the torus. There will no longer be an embedding.