MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

Let's flesh out Chris Godsil's answer after the recent bump.

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.