Question:
This is the problem I am having trouble on:

The crossing number of a graph G, denoted cr(G) is defined to be the minimum number of (pairwise) crossings of edges among all drawings of the graph in the plane. For example, cr(K5)=1 and cr(K3,3)=1.
What is cr(K7,7)?

I figured out that the answer is 81.

Now I am trying to figure out if K7,7 can be drawn in the plane with less than 81 crossings?

I'm not sure how to approach this one. Other than actually drawing it out and checking by trial and error, I am not sure how to approach this problem. Please help!

Thank you

Hi Christian,

cr(k7,7) is known to be either 77, 79, 81. In general the best known upper bound for cr(Km,n) is found by placing 'half' of the m points on each side of the origin on the X axis and 'half' of the n points on each side of the axis on the Y axis and adding up the crossing numbers from each of the four bipartite subgraphs formed in the quadrants - if there were p points and q points on the positive X and Y axes for example, then these can be joined with at most p choose 2 times q choose 2 crossings. Presumably you did this to get your 81. Consult any up-to-date graph theory book for more information.

Cheers,
Denis