Take the 2-minute tour ×
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.

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|improve this question
add comment

1 Answer

up vote 0 down vote accepted

Hint

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|improve this answer
add comment

Your Answer

 
discard

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