# How many non-homeomorphic surfaces arise from these graphs?

Take an undirected graph $G$, where every vertex has at least two edges (we count self-loops as two edges). For each vertex $v$, we define a regular deg($v$)-gon. For each edge between $v_1$ and $v_2$, we glue one of the edges of their polygon together (arbitrarily). We never glue an edge to itself.

This will give us a surface (which will be compact if $G$ is finite). How many surfaces will there be, up to homeomorphism (or how do you calculate this number, or establish bounds on it)?

Note that different surfaces can pop up, depending on how you glue things together. For example, a vertex with two self-loops, it can be a torus or a Klein bottle or a projective plane or a sphere.

We have $\Pi_{v\in V(G)}2(\text{deg($v$)}-1)!$ as an upper bound (the factor $2$ is because of orientation).

• (singular of vertices is vertex, just fyi) Commented Jan 23, 2018 at 19:44
• The answer is "1". Or maybe you mean, how many when $G$ varies... under which restriction? $G$ ranges over finite graphs? connected? with some restriction on the number of vertices?...
– YCor
Commented Jan 23, 2018 at 19:44
• @YCor I mean if you connect them in different orders. For example, Imagine that $G$ is a vertex $v$ with four self loops. Then the topology could be a torus, klein bottle, projective plane, or even sphere. Commented Jan 23, 2018 at 19:46
• For each vertex, to define a polygon, you need some cyclic ordering of the set of edges at this vertex. So this sounds ill-defined.
– YCor
Commented Jan 23, 2018 at 19:46
• The number of cyclic orderings at a given vertex $v$ of degree $d$ is much more than $2d$. It's $d!/d=(d-1)!$.
– YCor
Commented Jan 23, 2018 at 19:48