# Can all connected graphs be embedded on a closed, compact 2-Manifold?

I know that there are spherical (planar) graphs such as $$K_4$$,and toroidal graphs such as $$k_7$$, but I was wondering if given any connected graph $$G$$, there exists a closed, compact 2-Manifold $$M$$ such that $$G$$ can be embedded in $$M$$? If so, does the smallest possible genus of $$M$$ or whether or not $$M$$ is orientable tell us any properties of $$G$$?

• Commented Apr 27, 2020 at 10:45

For finite graphs, the answer is yes. (For infinite graphs, your embedding of the vertex set on a compact surface will necessarily have accumulation points, which is a bit of a mess.)

To see this, just draw the graph in the sphere, such that only two edges ever cross at a single point. By compactness, we can do this by just wiggling the edges a bit to prevent triple crossings. For each crossing, add a handle for one of the crossing edges to make a 'bridge' for the one edge to go over the other (in the diagram, the added handle, viewed from above, is in blue).

Note that this construction does not give the lowest genus surface possible for an embedding, it's just an easy argument to show such a surface exists.

The minimum genus is a useful piece of information. For each genus, there is a finite set of forbidden minor obstructions, per the Robertson-Seymour Theorem (much like $$K_{3,3}$$ and $$K_5$$ are obstructions for embedding on the plane or sphere). The genus also bounds the chromatic number of the graph (so an analog of the four-colour theorem holds for any compact surface). It is also sometimes possible to create more efficient algorithms for graphs of bounded genus than for arbitrary graphs.

I don't know anything regarding orientability however.

• For the Robertson-Seymour Theorem, if a graph $G$ is a forbidden minor obstruction of a genus $K$, does that mean it is not a forbidden minor obstruction for any other genus? Commented Apr 30, 2020 at 2:51
• For the orientable case, if $G$ is forbidden on genus $K$, it is also forbidden for any genus less than $K$. I'm not sure how things work in the non-orientable case, I'd assume it's similar. Commented Apr 30, 2020 at 8:19
• What I meant to say was that if there is a graph $G$ that was on the minimal list of forbidden minor obstructions for graphs of genus $K$ and $K+n$, then by your handle bar argument above, this tells me that the graph has $n+1$ unavoidable crossings when embedded on a surface of genus $K$. So if we removed one edge from $n$ of those crossings (call this graph $G’$), we’d still have one unavoidable crossing, making the list of forbidden minor obstructions of genus $K$ non-minimal since we don’t need $G$ in the list, only $G’$. So the minimal list for any two genus must be unique. Correct? Commented Apr 30, 2020 at 16:35