Problem: Let $G$ be a simple graph embedded on an orientable surface of genus $g$ with $n$ vertices. For which values of $n$ (depending on $g$ ) can we prove that the complement of $G$ is not embeddable on an orientable surface of genus $g$?
My attempt: The orientable genus of a graph is related to the number of crosscaps, which is essentially the number of "handles" on the surface.
Let $c$ be the number of connected components in $G$. Then, the genus of the surface on which $G$ is embedded is given by the formula $g = \frac{1}{2}(e - v + c + 1)$.
Now, consider the complement of $G$, denoted as $\overline{G}$. The number of vertices in $\overline{G}$ is the same as in $G$, i.e., $n$. The number of edges in $\overline{G}$ is given by $\binom{n}{2} - e$, where $e$ is the number of edges in $G$.
Apply the formula for the genus to $\overline{G}$:
$\overline{g} = \frac{1}{2}\left(\binom{n}{2} - e - n + c + 1\right).$
We want to find the values of $n$ for which we can prove that $\overline{G}$ is not embeddable on a surface of genus $\overline{g} = g$. This implies:
$\frac{1}{2}\left(\binom{n}{2} - e - n + c + 1\right) = \frac{1}{2}(e - n + c + 1).$
Simplify this equation: $\binom{n}{2} - e - n + c + 1 = e - n + c + 1.$
Cancel common terms: $\binom{n}{2} - e = e.$
Simplify further: $\binom{n}{2} = 2e.$
Now, recall that $e$ is the number of edges in $G$. Let $m$ be the number of edges in $\overline{G}$. Since $\overline{G}$ is the complement of $G$, we have: $m = \binom{n}{2} - e.$
Substitute this into the equation: $\binom{n}{2} = 2(\binom{n}{2} - m).$ Simplify: $\binom{n}{2} = \binom{n}{2} - 2m.$ This implies $m = 0.$
Therefore, the complement of $G$ can only be embeddable on a surface of the same genus if $G$ is a complete graph. In other words, if $G$ has all possible edges between its vertices, then the complement of $G$ can be embedded on a surface of the same genus.
This concludes the solution to part 2. The complement of $G$ is not embeddable on an orientable surface of genus $g$ unless $G$ is a complete graph.
I wonder if I have done everything well. Otherwise, I hope you could help me to correct the solution.
This is an interesting question, but there are a couple of mistakes. First of all, the formula you are citing is just incorrect. The genus of a surface is always integer, but the formula you cite can have $g$ be a non-integer, for instance the graph with one vertex and no edges. You should look into Euler's formula, which states that for a connected graph $G$ to be embeddable in a surface of genus $g$, then
$$ g\geq 1-\frac{1}{2}(e-v+f) $$ where $f$ is the number of faces of $G$. You can think of how this generalizes to graphs with $c\neq 1$.
Another problem is that you are assuming $G$ and $\overline{G}$ has the same number of components, which is not the case in general. Consider for instance $C_4$ whose complement is $2K_2$, the former is connected, whereas the latter has two components.
Intuitively your conclusion should raise some red flags since every graph is the complement of some graph, and we know that we can embed some graphs that are not cliques nor stable sets. A special class of graphs that might be worth consideration are graph that are isomorphic to their complement, for instance, $P_4$ or $C_5$. There are many such graphs, see https://oeis.org/A000171. I hope this helps.