1
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy