# What is the maximum number of edges in a planar bipartite graph which have partitions of order 7 and 15?

Over on the BoardAndCardGames beta we've been discussing a theoretical problem about the board game Carcassonne. While attempting to construct an upper bound on the maximum score we ran into the problem:

What is the maximum number of edges in a planar bipartite graph which have partitions of order 7 and 15?

By playing around on paper the answer appears to be 40, and this seems to have something to do with the Euler Characteristic and the three utilities problem, but I was wondering if there's a straight-forward proof.

Thanks!

-
Pardon my ignorance, but what does it mean for a graph to have a partition of order 7? –  01000100 May 24 '12 at 9:26
@DanielPietrobon I thought the two halves of a bipartite graph were called partitions? I'm asking about a bipartite graph with 7 vertices in one half and 15 in the other. –  tttppp May 24 '12 at 10:13
The correct term is bipartition. –  Jernej May 24 '12 at 11:49

If $G$ is a bipartite graph with $v$ vertices and $e$ edges then $e \leq 2v-4.$