Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

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.