A Parity Theorem For Drawings of Complete Graphs

This post gives a (hopefully) very accessible treatment of a beautiful mathematical fact of topological graph theory, called the “parity theorem” of Kleitman. (Two numbers have the same parity if they are either both even or both odd). (Please see this paper for a more conventional discussion).

Pick an odd positive integer, n. Draw the “complete graph” with n vertices (you may think of the vertices as dots, and between any two of them we draw a line. The lines do not need to be straight lines. The lines are called edges. The complete graph with n vertices is denoted K_n). In figure 1 we see two drawings of K_5, the complete graph with 5 vertices. Notice that both drawings (figure 1a and figure 1b) have an odd number of crossings.

In figure 2a there is drawing of K_5 with 4 crossings. However figure 2a has something that’s deemed a bit silly—two of the crossing edges (the red edges) both share a vertex (the bottom right vertex).

In general, there is a technical definition of a “good drawing” that prevents exactly this. There is a reason for this restriction: if two crossing edges are incident with the same vertex, then the drawing can be slightly modified to remove that crossing, without introducing any new crossings in the rest of the drawing, shown abstractly in figure 3a. It is common to ignore a drawing if it is “not good” (a drawing that is not good cannot be part of a drawing of K_n with the fewest number of crossings, for example).

Goodness also requires that edges don’t touch each other tangentially (figure 3b), a pair of edges don’t cross each other more than once (figure 3c), and that no edge crosses itself. If three edges happen to cross at the same point we consider it to be 3 crossings (some will simply insist that 3 edges do not cross at the same point, via a slight transition shown in figure 4, that would not affect any other crossings in the drawing).

Figure 2b shows what happens to the drawing in figure 2a after removing the crossing that is not “good,” and guess what? There are an odd number of crossings in the good drawing shown in figure 2b.

We will soon show that every good drawing of K_5 has an odd number of crossings. First, an easy fact: Every good drawing of K_3 must be without any edge crossings. Furthermore every good drawing of K_3 has an “inside” and an “outside”. If beyond the K_3 there are two other vertices, u and v, such that u and v are both on the same side of the K_3 (in figure 5 they are both outside the K_3), then an edge joining u to v must cross the edges of the K_3 an even number of times in total (possibly zero times if uv doesn’t cross the red K_3 at all. However, if you start to draw uv starting from u, and if your edge uv enters the inside of the red K_3 by crossing a red edge, then it must also return to the outside of the red K_3 to get to v—resulting in a second crossing involving uv. So if there is a crossing involving uv, there must be at least 2 crossings of uv with the red K_3, etc…) Similarly, if u and v are on opposite sides of the K_3 (one is outside but the other is inside) then the edge uv crosses the K_3 an odd number of times. (This simple idea will come in handy when we analyze figure 7 below).

Next, to review and reinforce your understanding of the “goodness” criteria, convince yourself that every good drawing of K_4 has at most 1 crossing. If you try to draw K_4 with two or more crossings, there will be a goodness violation (probably there will be one vertex incident with 2 crossing edges—there are only 4 vertices, so check them all!)

In any case, the upshot is that each crossing requires 4 vertices and actually, the crossings in a drawing of K_5 can be counted by counting the K_4’s that have a crossing.

This may seem much harder than just counting the crossings, but it works well on an abstract level—that is, when we don’t know what the drawing looks like, but still have to prove things about it. This is what makes the theorem and its proof beautiful—we will prove there is something common to infinitely many different drawings of K_5.

To make this abstract approach more concrete, look at figure 1b–if we remove the top vertex and its incident edges, we end up with a K_4 with a crossing in it (figure 1c). If on the other hand, we start with figure 1b and remove the bottom vertex and its incident edges, we get a K_4 that does not have a crossing (figure 1d).

There are three other vertices we could have deleted to get a K_4 (try to draw them!) Only one of the five vertex-deleted K_4’s has a crossing. We see in a different way (other than directly counting crossings) that there is one crossing in the K_5.

Now consider figure 1a. If we delete the bottom vertex and all its incident edges, we are left with a K_4 with 1 edge crossing–the crossing highlighted in red.

As there are 5 vertices you could have deleted, there are 5 different drawings you need to make from figure 1a, each with a different crossing (try it, at least mentally), so we see in a different way that there are 5 crossings in figure 1a.

For a given drawing, if all five of the vertex-deleted K_4’s have a crossing, then the K_5 has 5 crossings, which is an odd number. A good drawing of K_5 either has 5 crossings or else we can find a K_4 inside it so that if we just look at that K_4, it does not have crossings. This motivates:

Lemma: Suppose a drawing D of K_4 has no edge crossings. Suppose that D is part of a good drawing D’ of K_5. Then D’ has an odd number of crossings.

We have an example of a drawing of K_4 without crossings (see figure 6). There is an extra vertex v that we wish to use to extend the K_4 to a drawing of K_5. Although this is a specific picture, there are features of it that are always true. In particular, deleting the edges incident with a specified vertex of the K_4 will result in a K_3 with an inside and an outside (we obtain figure 7a from figure 6 by deleting the edges incident with the vertex ‘a’. Both ‘a’ and ‘v’ are outside the remaining K_3 with vertices b,c and d). This looks like figure 5!

If we wish to count the total number of crossings of a K_5 that involve the edge va, then we should not look at the other edges incident with ‘a’, since the edge va can’t cross them anyway (by goodness–two edges incident with ‘a’ cannot cross each other). Also, va can’t cross the other edges incident with ‘v’ (also by goodness–two edges incident with ‘v’ cannot cross each other), so we won’t worry that we can’t see the edges incident with ‘v’ in figure 7a.

When we count the number of times va crosses anything in the K_5, it must be an even number since ‘v’ and ‘a’ are both on the outside of the K_3 with vertices b,c and d. A similar argument (looking at figure 7b and the K_3 with vertices a,c and d) shows that vb crosses an even number of times. (Note that the va crossings are all different from the vb crossings, by goodness again!).

The number of times vc crosses in D’ is similarly even (see figure 7c); but the number of times vd crosses in D’ is odd, since v and d are on opposite sides of the K_3 made up of a,b and c as shown in figure 7d.

To summarize: All of the crossings of D’ will involve v, since D has no crossings. We add together the number of times each of the edges va, vb, vc and vd cross anything in D’ to get the total number of crossings in D’. Exactly three of these four numbers are even, so the sum is odd. By “goodness,” these numbers represent distinct crossings, (no single crossing can involve two edges incident with ‘v’) and as such these crossings can be added together meaningfully.

All of these facts depended only on the fact that we started with a drawing of K_4 with no crossings, and not the particular drawing in figure 6. (Imagine ‘v’ had been in a different location, for example, very close to ‘d’ inside the K_3 bounded by a,b and c. Check that the argument still works!)

This essentially proves the lemma. Together with the discussion before the lemma, we now know that every good drawing of K_5 has an odd number of crossings. We’ve also seen that every good drawing of K_3 has zero crossings (and zero is even, so “every good drawing of K_3 has the same parity as every other good drawing of K_3” is a true statement) and we know that K_4 has a good drawing with 0 crossings and another good drawing with 1 crossing (so no parity theorem for good drawings of K_4).

Based on these 3 (measly) examples, n=3, n=4 and n=5, we are now ready to state the theorem. For it’s short proof, miraculously, no more geometry is needed:

Theorem (Kleitman): Let n be an odd integer, and D be a good drawing of K_n. Then the number of crossings in D has the same parity as the binomial coefficient “n choose 5”.

Before getting to the proof, here is an example with n=7 to illustrate the idea of the proof. If you have 7 objects, there are 21 ways to select exactly 5 of them (try it). So we say “7 choose 5” is 21. In our context, we count crossings in a K_7 by separately counting the number of crossings in each of the twenty-one K_5’s in the K_7. (This counts each crossing more than once—hmm…but we don’t want the number of crossings, we want the parity of the number of crossings… More explanation to follow!)

Each of these twenty-one numbers is odd (since each of the twenty-one K_5’s has an odd number of crossings). So the sum of the 21 numbers is also odd. When we add these 21 numbers, every crossing would have been counted 3 times (a crossing requires 4 vertices; when you look at a single crossing it therefore belongs to 7-4=3 different K_5’s). So our odd sum of 21 numbers, divided by three, is the number of crossings in the K_7. We don’t know what the number of crossings is (that’s why we didn’t try to count the exact number of crossings), but we know the number is odd, since an integer that is obtained from odd integer divided by 3 is necessarily odd.

In general, to find the number of crossings in any good drawing of K_n, we add “n choose 5” different (unknown, but definitely odd) numbers together and divide by the odd number (n-4) to get the exact number of crossings…And we don’t know what the exact number is but we also don’t care; the sum of “n choose 5” odd numbers must have the same parity as “n choose 5” (regardless of what integer “n choose 5” turns out to be). If this sum is divided by an odd integer and the quotient happens to be another integer, then this quotient also has the same parity as “n choose 5.” But we divide by n-4, which is odd since n is odd. So this completes the proof.

Remarks:

1. This presentation is a first attempt at a response to the criticism: “Why don’t mathematicians or scientists ever write the way they think?” In fact, this “unnecessarily” long exposition does not mean that it is difficult; my hope is quite the opposite. The length of this post is an attempt make it as lucid as possible, for as large an audience as possible. I welcome feedback to improve the clarity, and to reduce the prior expectations on the reader.
2. This discussion is much different from Kleitman’s original approach. For a full discussion, please see the paper: A Parity Theorem for Drawings of Complete and Complete Bipartite Graphs, by Dan McQuillan and R. Bruce Richter, in the American Mathematical Monthly, Vol. 117, No. 3 (March 2010), pp. 267-273. Furthermore, there are several other topics in the paper not covered in this post. Please check it out and enjoy!