# Say i have $n$ points in the plane all of which are connected. What is the minimum number of intersections between the connecting lines?

Say i have $n$ points in the plane all of which are connected with segment lines. What is the minimum number of intersections between the connecting lines?
Note 1: We count the number of intersections not intersection points, so even if three lines intersect in 1 point that's 3 intersections.
Note 2: There can not be 3 points in a line.
Here is the case for n=5 with one intersection.

• Are the lines infinite, or just segments? – Bernard Aug 2 '16 at 13:17
• @Bernard Segments. – SoloNasus Aug 2 '16 at 13:19
• Can be three points in a line? – mfl Aug 2 '16 at 13:31
• @mfl no three points in a line – SoloNasus Aug 2 '16 at 13:38
• – Marcus Andrews Aug 2 '16 at 14:13

## 1 Answer

You are trying to find the crossing number of the complete graph $K_n$. As you'll see in the link, the best upper bound on the crossing number is $$\frac{1}{4} \left\lfloor \frac{n}{2} \right\rfloor \left\lfloor \frac{n-1}{2} \right\rfloor \left\lfloor \frac{n-2}{2} \right\rfloor \left\lfloor \frac{n-3}{2} \right\rfloor.$$ It is known that the crossing number equals this upper bound for $n=5, 6, \ldots, 12$ and it is conjectured to hold for all $n \geq 5$.

• That seems to be exactly what I was looking for. Is the upper bound rigorously proven though? – SoloNasus Aug 2 '16 at 14:32
• Yes, the upper bound part has been proved – D Poole Aug 2 '16 at 14:45