# 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
add comment

## 2 Answers

From Euler's formula one can derive the following estimate

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

So the bound you stated is clearly valid. To show that it is sharp you need to construct a graph of order 22 having 40 edges and two bipartitions of size 15 and 7. I don't know how to do that though.

-
add comment

Complementary to Azoo's answer, it's not hard to construct such a graph with 40 edges. Put the fifteen on a line. Put one of the seven on one side of this line, and join it to each of the fifteen. Put another one of the seven on the other side of the line, and join it, too, to each of the fifteen. That's thirty edges already. Now put each of the remaining five of the seven between two of the fifteen, and connect each of the five to each of the two. That's ten more edges, making forty.

-
add comment