# "incidental" intersections of a complete graph in the plane

Given a complete graph of n vertices (no three of which are no collinear) in the plane and straight edges, what is the maximal possible number of "incidental intersections" of edges, i.e., number of non-vertices at which two distinct edges intersect each other, not counting multiplicity?

This is a question that I pose to the students in my Mathematics for Elementary School Teachers as a way to understand mathematical conjecturing and proving -- and not always finding the solution. But it occurs to me that it might be handy to know whether the answer is actually known or not.

• I assume you're drawing the edges as straight line segments? Oct 21 '10 at 10:06
• If multiple intersections are forbidden, it is open problem: en.wikipedia.org/wiki/Crossing_number_(graph_theory) I do not see, why it should be easier if they are permitted (and not counted)... Oct 21 '10 at 11:40
• Fedor, I think what's open is the crossing number, which is the minimum number of non-vertex intersections, but OP is asking for the maximum. Oct 21 '10 at 12:38
• Indeed! But then the answer is $+\infty$? Or edges are supposed to be line segments? Oct 21 '10 at 12:57
• Reminds me of a problem discussed in amazon.com/Out-Labyrinth-Setting-Mathematics-Free/dp/0195147448, which you should totally read if you're teaching Mathematics for Elementary School Teachers. I used that exact problem with a Math Circle of 7-year-olds a few years ago, and it went over well. Oct 21 '10 at 15:09

Assuming straight line segment edges, any 4 vertices determine 6 edges with at most one non-vertex intersection, so you can't have more than $n$-choose-4. You will have $n$-choose-4 if no vertex is interior to any triangle of vertices, which is to say if all $n$ vertices lie on the boundary.

• This isn't enough; for example, if the vertices lie at the nth roots of unity then lots of edges will intersect at the origin. You need some kind of general position requirement. Oct 21 '10 at 11:30
• @Qiaochu, you are right, to get $n$-choose-4 you must arrange that no three lines meet at a non-vertex point. Of course, that's easily done; if three meet, just move one vertex a tiny bit. Oct 21 '10 at 12:35

This problem (although phrased slightly differently) is #1.3.5 in Loren C. Larson's "Problem Solving Through Problems."

The rephrase of this is, "On a circle, n points are selected and the chords joining them in pairs are drawn. Assuming no three of the chords are concurrent (except at the endpoints), how many points of intersection are there?"

This is $\binom{n}{4}$, as any four of our points on the circle determine a (unique) intersection point, and any intersection point determines the boundary chords.

[This might've been better as a comment on Gerry's answer, but there's a whole family of similar problems to the question asker's in that chapter of the book (which are also excellent problems to give to a math club.)]

• Thanks for the citation -- I didn't know about this book, to my embarassment. I like the almost Zen-like redundancy of the tile. Oct 22 '10 at 11:28
• The nice continuation of this problem is, with the construction above, how many regions did you break the circle into? The pattern at the beginning is (for n=# points on the circle): 1,2,4,8,16... Then 31. It's another good counterexample to the, "Test the first five cases then make a conjecture." Oct 22 '10 at 12:28

If you let me do something silly, then I can put all the points in a line. Technically this gives an infinite number of points of intersection, since every point on the line segment is a point of intersection of two edges. If instead I count the number of pairs of edges which contain a non-vertex in their intersection then I still get

\begin{equation*} \binom{\binom{n}{2}}{2} - \sum_{1 < i \leq j < n} (i-1)(n-j), \end{equation*}

which I guess is maximum (it's more than $\binom{n}{4}$).