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?
$\begingroup$
$\endgroup$
3
-
3$\begingroup$ 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. $\endgroup$– Chris GodsilJun 7, 2011 at 23:46
-
$\begingroup$ I think you can post it as an answer!! $\endgroup$– TurboJun 7, 2011 at 23:49
-
$\begingroup$ Could you please provide a reference as well? $\endgroup$– TurboJun 7, 2011 at 23:53
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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$.
answered Feb 11, 2014 at 10:24