# Ore's “Graphs and Their Uses” Problem Set 1.5, Problem 2 …

Ore's classic book asks for a proof of the following. Is my proof correct?

Show how each of four neighbors can connect his house with the other three houses by paths which do not cross (this is the part of Problem 1, which I have solved). A fifth person builds a house nearby; prove that he cannot connect his house with all the others by non-intersecting paths, but that he can connect it with three of the others.

Let’s say that the fifth person’s house is e and the (closed) curve C is formed by the four houses is abcda, where each of the four houses is connected to the other three. Let the curve ac lie inside C and curve bd lie outside C (both ac and bd can’t be simultaneously lying inside or outside C without intersections).

There are three possibilities to consider for the new house e:

1. e lies inside C.
2. e lies outside C.
3. e lies on C, between any two existing houses (say a, b).

In the first case, e could be trivially connected to a, b, and c or a, d, and c without intersections (depending upon whether e lies with respect to the closed curve abca or closed curve acda). If e lies inside curve abca, we can’t connect e (which lies inside abca) to d (which lies outside abca) without intersecting the curve abca (according to Jordan’s curve theorem). Similar reasoning applies if e lies inside the curve acda (in which case b lies outside acda). This proves that in this case, e can be connected to any three, but not all four houses without intersections.

In the second case, say that e lies outside the curve C such that we form a new curve C’ by connecting ae, eb, bc, cd, da, ae. We clearly keep the two existing curves ac (that lies inside C and also inside C’) and bd (that lies outside C and also outside C’). There are no intersections yet since we have two non-intersecting curves ab and ac inside curve C’ and two non-intersecting curves ed and bd that are outside C’. But if we try to connect e to c so that ec lies inside C, it must intersect ab whereas it must intersect bd if we connect them so that ec is outside C’. Thus, e can be connected to a, b, and d without any intersections, but can not be connected to c without an intersection.

In the third case, consider that e lies on the curve C and we now have C formed by ae, eb, bc, cd, da. We retain ab (inside C), ac (inside C), and bd (outside C) without any intersections. We can also connect ed so that it lies outside, thus connecting e to a, b and d (three houses). But if we connect e to c such that ec is inside C, then it intersects ab which is also inside and if we connect e to c such that ec is outside C, it intersects bd. In either case, we have an intersection.

In fact this proof is a rather well-known one, and you've essentially proven that $K_5$, the complete graph on five vertices, is non-planar. Googling the phrase "proof that K5 is nonplanar" will return some non-trivial results, and you can compare your proof with others if you wish. It appears that most proofs of this make use of a corollary to Euler's formula:
Given a planar graph with $e$ edges and $v$ vertices, we must have $e \leq 3v-6\;$.