MathOverflow is a question and answer site for professional mathematicians. 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

Suppose we have a finite connected graph $G$, I want to add 2 -cells to $G$ so that the 2 cells have boundaries of length 4 (squares) and so that $G$ is the 1 skeleton of a surface (2-manifold) without boundary. To check that such a process can be done to $G$ does it suffice to check whether each edge in $G$ occurs as an edge of 2 distinct 4 -cycles? does it suffice to check if each edge occurs as exactly 2 distinct 4 cycles? Is there a known sufficient condition?

share|cite|improve this question
No, that won't suffice. What you need to check is primarily at the vertices. If a 2-cell is incident to a vertex, it gives an ordering of the two edges that it is incident to at that vertex. What you need is that this gives a cyclic ordering of the edges incident. In principle, you could have a non-cyclic ordering, for example, you could have two disjoint cycles. This is what you'd get if you wedged two planar graphs together along a common vertex. – Ryan Budney Mar 26 '13 at 21:18
@Ryan, Do you know of a sufficient condition so that this process can be done? – Antony Della Vecchia Mar 26 '13 at 21:40
What I mentioned is a necessary and sufficient condition. The edge condition that you mention is a consequence of the vertex condition I describe in my original comment. – Ryan Budney Mar 26 '13 at 21:44
Alright, thanks – Antony Della Vecchia Mar 26 '13 at 22:43

Your Answer


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

Browse other questions tagged or ask your own question.