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 tried solving this problem using permutations, as 15P6=3603600, which doesn't seem to be right. Please advise.