Question 1:
- Let $G$ be a graph embedded on an orientable surface of genus $g$, not necessarily cellularly. Prove that $v-e+f \geq 2-2 g$, where $v, e$ and $f$ denote respectively the number of vertices, edges and faces of the graph embedding.
My attempt:
The general form of Euler's formula for a surface of genus $g$ is $v-e+f \ge 2-2g$. In a non-cellular embedding, there might be fewer faces or edges might be shared more than twice, leading to $v-e+f$ being less than what it would be in a cellular embedding. This justifies the inequality $v-e+f \ge 2-2g$ acknowledging that some faces may be missing or not fully formed compared to a cellular embedding.
Question 2
- Let $G$ be a simple graph cellularly embedded on an orientable surface of genus $g$, with the properties that (1) all the faces have degree three (i.e., are incident to three edges), and (2) each cycle of length 3 in the graph bounds a face. The set of such (triangular) faces is denoted by $T$. Use the previous question to show that in any embedding of $G$, the number of faces is $|T|$. Deduce that the embedding of $G$ on an orientable surface of genus $g$ is unique up to homeomorphism.
My attempt: We have: Since all faces have degree three and each cycle of length 3 bounds a face, every face in $G$ is a triangle.\ The number of faces $f$ in $G$ is equal to the number of triangular faces, which is $|T|$.
For the second part, I still get stuck. Could you please help me with solving the second part? Many thanks.