There are ten roads linking all possible pairs of five cities. It is known that there is at least one crossing of two roads, as illustrated in the diagram below on the left. There are nine roads linking each of three cities to each of three towns. It is known that there is also at least one crossing of two roads, as illustrated in the diagram below on the right. Of the fifteen roads linking all possible pairs of six cities, what is the minimum number of crossings of two roads?
I used the formula suggested by H. F. JENSEN in his paper "An Upper Bound for the Rectilinear Crossing Number of the Complete Graph" ; with n=6 cities/nodes as : number of crossings <= (7*(6^4)-56(6^3)+128(6^2)+48*6*((6-7)/3)+108)/432 i.e. number of crossings <= 3.69444 i.e. the crossing number for 6 nodes is at most 3 (since the number of crossings should be a whole number). Is this correct? Please advise.
At "least" 3 crossings........