Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
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!! –  J.A Jun 7 '11 at 23:49
    
Could you please provide a reference as well? –  J.A Jun 7 '11 at 23:53
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.