Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Given a connected graph $G=(v,e)$ with the condition that each vertex of G lies on either 1 or 0 cycles, can $G$ be 2-cell embedded on any surface other than a sphere?

I know the maximum genus $[G \le B(G)/2]$ with $B(G)=|E|-|V|-1$ because $G$ is connected, but I'm not sure if the cycle limitation on the graph affects this condition. It seems that you could begin with a cycle, add a vertex attached to only one member of the previous cycle, then add more vertices create a new cycle containing the added vertex, and repeat. Each iteration adds one more edge than vertex (adding a 3-cycle adds 3 vertices and 4 edges) so this technique could be used to construct graphs with arbitrarily large $B(G)$.

share|cite|improve this question
up vote 0 down vote accepted


You can use induction on the number of cycles in the graph, and how adding a cycle increases $B(G)$ and $\epsilon_0(G)$ respectivey.

share|cite|improve this answer

Your Answer


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