# Maximum fixed genus Bipartite graphs

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with $n$ vertices of color $1$ and with $n$ vertices of color $2$.

What is the maximum number of edges that a genus $g$ graph $B_{n,n}$ can have? Are there any good references for this topic?

-
It's an easy exercise to show that if $B$ is simple and bipartite and embeds in an orientable surface of genus $g$ then $$|E(B)| \le 2|V(B)| - 4 + 4g$$ and equality holds if and only if each face has degree four. –  Chris Godsil Jun 7 '11 at 23:46
I think you can post it as an answer!! –  Turbo Jun 7 '11 at 23:49
Could you please provide a reference as well? –  Turbo Jun 7 '11 at 23:53

Euler's formula tells us that $V-E+F=2-2g$, where $V$, $E$ and $F$ are the number of vertices, edges and faces respectively in an embedding of $G$. The smallest possible faces in an embedding of a bipartite graph are 4-cycles, so, by counting the edges round each face, $E \geq 4F/2$, i.e. $F \leq E/2$, with equality if and only if all faces are 4-cycles. Rearranging gives $E \leq 2V -4 + 4g$.