# Smallest planar graph with two non-homoemorphic plane embeddings?

What is the smallest (not necessarily simple) planar graph with two non-homeomorphic embeddings into the plane?

I am interested in both the case where vertices are labelled, and also the case where they are unlabelled. (In my application, vertices are labelled, but labels need not be unique.)

As a follow-up, what is the smallest planar graph with inequivalent embeddings onto the sphere?

(In case it makes a difference, I assume that graphs are undirected.)

• A triangle with an extra edge pointing in, resp. out? I don't think one can do better... Nov 10, 2017 at 14:10
• For the sphere, take the triangle with two extra edges, pointing into the same, resp. different hemispheres Nov 10, 2017 at 14:11
• If we don't have to be simple, then a double edge will serve in place of a triangle. Nov 10, 2017 at 14:12
• if you allow non-simple graphs, the triangle can be degenerate (i.e. two parallel edges, or even a loop --- if loops are allowed) Nov 10, 2017 at 14:13
• Hello Ross! You might also have a look at Tutte's census paper, in particular Figures 3 and 4. Figure 3 shows the nine different rooted planar embeddings of the four two-edge graphs. If you consider unrooted embeddings into the plane, then the two-vertex graph with one bridge and one loop still has two different embeddings. Nov 10, 2017 at 14:17