There exist graphs which don't have a 2-cell embedding in any non-orientable surface (take $C_n$, for example). Is it true that any finite graph with this property must be planar?
Define the non-orientable genus of a graph $G$, $\tilde{\gamma}(G)$, as the minimum non-orientable genus among all surfaces in which $G$ can be 2-cell embedded (With $\tilde{\gamma}(G)=0$ if $G$ is one of the graphs described above). If $e$ is an edge in $G$, does this imply that $\tilde{\gamma}(G\setminus\{e\})\leq \tilde{\gamma}(G)$?