Math Central - mathcentral.uregina.ca
Quandaries & Queries
Q & Q
. .
topic card  


crossing number

list of
. .
start over

One item is filed under this topic.
Crossing number 1999-11-06
From Christian:
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!
Answered by Denis Hanson.




Math Central is supported by the University of Regina and The Pacific Institute for the Mathematical Sciences.



Home Resource Room Home Resource Room Quandaries and Queries Mathematics with a Human Face About Math Central Problem of the Month Math Beyond School Outreach Activities Teacher's Bulletin Board Canadian Mathematical Society University of Regina PIMS