Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in a certain class of graphs but have very little graph theory background, I was hoping that you guys could poke me in the right direction. The class of graphs is as follows:

  • Multi-graph
  • Connected components are directed Euler graphs
  • Minimal degree is $4$
  • Bipartite
  • We are given an embedding in $X$, a compact orientable surface of genus $g$.
  • The faces of the graph (when considering said embedding) are $4$-colourable.

I'm interested in any property of these graphs!

Thanks in advance!

share|cite|improve this question
If the graph isn't planar, then what do you mean by the dual graph? – Gerry Myerson Mar 6 '12 at 22:38
Sorry, dual when it's given the embedding in the surface of genus $g$. I will fix this now. – Harry Mar 6 '12 at 22:43
Bump for information. – Harry Mar 8 '12 at 14:03
One last bump for info. – Harry Mar 19 '12 at 16:44
You might get better answers if you say why you became interested in this particular group of properties. Do these graphs arise in some problem you are trying to solve? – MJD May 4 '12 at 13:30

OP has clarified in the comments that some equations are wanted.

Assuming that the embedding in $X$ is a 2-cell embedding (that is, that each region is homeomorphic to a disk) we have Euler's formula, $$v-e+f=2-2g$$ where $v,e,f$ are the number of vertices, edges, and faces, respectively.

For any graph, $2e=\sum_x d(x)$, the sum over all vertices $x$ of the degree of $x$. Since the minimal degree is 4, we get $$e\ge2v$$

I think the 4-colorability gives another inequality relating these invariants, but I'm not remembering how to find it.

share|cite|improve this answer
It is not necessarily connected - shouldn't it be $v - e + f = 1 - 2g + k$ where $k$ is the number of connected components? Also I would really appreciate it if you could post the $4$-colourability inequality. I've thinking of getting Topological graph theory by Tucker and Gross, is this a good idea? – Harry May 13 '12 at 10:00
How can it be an Euler graph, if it's not connected? You may find something of interest in – Gerry Myerson May 13 '12 at 12:47
Doh! All connected components should be Euler graphs. Fixed question. Thanks for link - will read. – Harry May 13 '12 at 15:34

This is not a complete answer, but a sketchy response to one of Gerry Myerson's comments. Yes, infinitely many graphs satisfy the listed conditions.

Fisk and Mohar [JCTA 1994] proved that any undirected graph $G$ with the following properties is 4-colorable:

  • The shortest cycle in $G$ has length at least four.
  • $G$ can be embedded on a surface of genus $g$.
  • The shortest separating cycle in the embedding of $G$ has length at least $1000\,\log_2(g+1)$. A cycle is separating if it cuts the surface into two pieces. (The constant $1000$ is a conservative estimate; Fisk and Mohar prove the existence of an appropriate constant, but don't give any explicit value.)

It is fairly easy to construct arbitrarily large graphs $G$ that satisfy these requirements by subdividing any triangulation of the surface. The faces of the dual graph $G^*$ are 4-colorable (by definition of "dual"). Subdividing each edge of $G^*$ with a new vertex makes the dual graph bipartite. Finally, replacing each undirected edge with a pair of opposing directed edges makes the graph Eulerian with minimum degree $4$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.