3
$\begingroup$

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!

  • 0
    The correct term is bipartition.2012-05-24

3 Answers 3

4

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.

3

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.

0

Let the partitions have orders m and n. If m=1, the graph is planar and so the answer is n. Likewise, if n=1, the answer is m.

If m=2 or n=2, the graph is also planar and so the answer is mn. Note that mn=2(m+n)-4;

Now let m>2 and n>2. We claim that the maximum size of a planar subgraph is 2(m+n)-4. Choose m-2 vertices from the m-set and choose n-2 vertices from the n-set. Delete all edges involving these vertices. The number of edges deleted is (m-2)(n-2). The remaining edges is easily seen to form a planar graph. The size is mn-(m-2)(n-2)=2(m+n)-4. This must be the maximum because it is known that the maximum size of a planar bipartite graph of order v (at least 3) is 2v-4.