In 1978 or so, in seventh grade at St. George, a Catholic elementary school in Baton Rouge, one of my favorite teachers was Mr. Owens. In 1989, when I was in grad school, I sent him the following letter (somewhat edited here). He was by then the principal of St. George and a friend who visited years later said he saw a copy of my letter pinned on the bulletin board being Mr. Owens’s desk. I took that to mean he was happy to have gotten the letter. He passed away a few years ago.
***
Sunday, July 30, 1989
Mr. Jim Owens, Principal
St. George Elementary School
7880 Siegen Lane
Baton Rouge, LA 70809
Dear Mr. Owens,
I don’t know if you remember me or not. I used to be a student of yours at St. George, when I was in the 7th grade. I think that was in 1978 or so. You taught me religion.
You might not remember this either, but I haven’t forgotten. You always gave us puzzles and riddles to work out. For example, if you have 99 marbles of one color and 1 of the other color in a bag, what is the most you would have to pull out to be sure what the dominant color is. Or, in the famous Alpha (truth tellers) and Beta (liars) puzzle, what do you ask the native at the bridge to see if the bridge is safe. Etc. [The solution is: you ask the native: if you were a member of the other tribe, and I asked you if the bridge were safe to cross, what would you answer? And then the answer is the opposite of the answer.]
Well, one puzzle you gave us was: if you have three cities at the top, and three at the bottom, can you draw a road from each city at the top to each at the bottom without crossing roads? We tried and tried, all of us students, to get that one; no one could find a solution. We always had to cross some lines. When we told you we thought it was impossible, you said, “Ahh, but can you prove it’s impossible?” Which none of us could.
I am writing to present you with the proof.
(Also, I just called Mrs. [X] to find out St. George’s address, and she told me you are the new principal there. Congratulations and good luck with the job.)
Before I give you the proof, I guess I can tell you a little bit about what I have been doing since 7th grade. [omitted]
One of the courses I took in 1988 towards my MSEE was a math course (graph theory) where I learned how to do the proof below. …
I guess the reason I am writing is because I have never forgotten your challenge: “Ahh, but can you prove it’s impossible?” Also, because you were one of my most memorable teachers. … I was very interested in your ideas on “The Kingdom,” etc., at the time, if you’ll recall …, I still retain a passionate longing for the truth, a sense of independence, self-esteem, and a belief in the goodness possible to man, which are all traits I believe you helped me develop. …
So I thought I would present you with a proof of that problem. I don’t know if you yourself know the proof; not much graph theory is needed to prove it. Actually, it is the Jordan Curve Theorem (used in the proof) that does much of the work. That theorem is proved in high-level graduate math, but it is intuitively obvious. So here it is.
***
The three town to three town system we want to draw, in the stated problem, can be represented by a standard type of graph, called Kn,n. A Kn,n graph is one in which n vertices are completely connected to another group of n vertices. Thus a K3,3 graph will be one in which the three “top” towns are each connected to each of the three “bottom” towns. See Figure 1. In this drawing, some of the roads (hereafter called “links”) do cross each other.
Fig. 1
Now a planar graph is one which can be represented without any links crossing each other. Thus it is our task here to show that K3,3 is not planar; that it cannot be represented without any links crossing each other; that, to draw K3,3, some links must cross each other.
Proof: First, we must note the Jordan Curve Theorem. This theorem states, first, that any closed curve J separates the plane into two disjoint sets: the interior and exterior of J, denoted by int(J) and ext(J). The theorem states, secondly, and importantly, that any line joining a point in int(J) to a point in ext(J) must meet J in some point. Although this is easy to see, it is very difficult (but possible) to prove.
So let us partially (re-)draw the graph K3,3. We know that v1 and v2 must each connect to each of the three u-vertices. So let’s put v1 on top, the three u-vertices in the middle, and v2 on the bottom (see Figure 2). Let me briefly prove that we can always draw these five vertices in this manner (since this drawing is essential to the rest of the proof). First, for the graph to be planar, all the links in this figure must be present; and they must be drawable without crossing each other. Specifically, the curve C = u1v2u3v1u1 must always exist, since its component links are roads that must exist. Now either u2 is in int(C) or in ext(C). If it is in int(C), then we have the situation shown. If it is in ext(C), then either u1 or u3 will instead be in the interior of the other two. And in this case we could simply re-label vertices so that the vertex in the interior of “C” is u2. So we must have part of K3,3 drawable as in Figure 2.
Fig. 2
And we finally note that the area int(C) is composed of two distinct areas: int(C1) and int(C2), where C1 = u1v1u2v2u1 and C2 = u2v1u3v2u2. Also note that u1 is in ext(C2), u3 is in ext(C1), and u3 is in int(C2).
Now, with Figure 2 as shown, the final, sixth vertex, v3, can only be in one of two places: in ext(C) or in int(C).
(i) v3 in ext(C). Then there must be a link from v3 to u2. But this link would then go from ext(C) to int(C); so this link must cross one of the links composing C.
(ii) v3 in int(C). But since int(C) = int(C1) + int(C2), in this case v3 must be either in int(C1) or in int(C2).
(a) v3 in int(C1). Then there must be a link from v3 to u3. But this would then go from int(C1) to ext(C1); so this link must cross one of the links composing C1.
(b) v3 in int(C2). Similar to (a) above, the link from v3 to u1 would have to cross one of the links composing C2.
Thus, in both (or all three) situations, which are the only situations that can exist, a link from v3 would cross one other link. Thus, K3,3 is not planar, and it has been proven that it is impossible for roads to run from each of the three top cities to each of the three bottom cities without crossing each other.
Your humble student,
Stephan Kinsella
