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 K_{n,n}. A K_{n,n} graph is one in which n vertices are completely connected to another group of n vertices. Thus a K_{3,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.

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 K_{3,3} is not planar; that it *cannot* be represented without any links crossing each other; that, to draw K_{3,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 K_{3,3}. We know that v_{1} and v_{2} must each connect to each of the three u-vertices. So let’s put v_{1} on top, the three u-vertices in the middle, and v_{2} 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 = u_{1}v_{2}u_{3}v_{1}u_{1} must always exist, since its component links are roads that must exist. Now either u_{2} 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 u_{1} or u_{3} 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 u_{2}. So we must have part of K_{3,3} drawable as in **Figure 2**.

And we finally note that the area int(C) is composed of two distinct areas: int(C_{1}) and int(C_{2}), where C_{1} = u_{1}v_{1}u_{2}v_{2}u_{1} and C_{2} = u_{2}v_{1}u_{3}v_{2}u_{2}. Also note that u_{1} is in ext(C_{2}), u_{3} is in ext(C_{1}), and u_{3} is in int(C_{2}).

Now, with **Figure 2** as shown, the final, sixth vertex, v_{3}, can only be in one of two places: in ext(C) or in int(C).

(i) v_{3} in ext(C). Then there must be a link from v_{3} to u_{2}. But this link would then go from ext(C) to int(C); so this link must cross one of the links composing C.

(ii) v_{3} in int(C). But since int(C) = int(C_{1}) + int(C_{2}), in this case v_{3} must be either in int(C_{1}) or in int(C_{2}).

(a) v_{3} in int(C_{1}). Then there must be a link from v_{3} to u_{3}. But this would then go from int(C_{1}) to ext(C_{1}); so this link must cross one of the links composing C_{1}.

(b) v_{3} in int(C_{2}). Similar to (a) above, the link from v_{3} to u_{1} would have to cross one of the links composing C_{2}.

Thus, in both (or all three) situations, which are the only situations that can exist, a link from v_{3} would cross one other link. Thus, K_{3,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