Question of Session 5: Dwellers of Flatplanet are hostile creatures. Their countries don't even share borders, but are well separated from each other. There are six countries in total, three of them are the Allies, and the other three are, not surprisingly, the Axis. For strategic reasons, each country is topologically connected. An embedded correspondent is informing us that the shortest distance from any of the Allies countries to any of the Axis countries is equal to 1 flatkilometer (a unit of length widely used on Flatplanet). Could she be right?
Model
Assuming that our correspondent’s testimony is true, we model each Allied nation L1, L2, L3 as a topologically connected set of points in euclidean space. As has been provided, they do not share borders. We define sets of points L1+,L2+,L3+ as the points that are less than 1 fkm away and L1e, L2e, L3e as the points that are exactly 1 fkm away from the nearest point in L1, L2, and L3 respectively. We also define the sets X1, X2, X3, each representing a topologically connected piece of Axis territory.
Now we can remodel the map as a graph G containing the points l1, l2, l3, x1, x2, x3 with the following rule: If the set Xn shares at least one point with the set Lme (and does not share any point with Lm+), then there is an edge xnlm in G. Given the known information and the testimony of our correspondent, every edge xnlm (n,m∈{1,2,3}) is an edge existing in G. The resultant graph turns out to be identical to the complete bipartite graph K3,3.
K3,3 represents the countries of Flatplanet situated on a topological surface. Each edge in the graph K3,3 corresponds to a set of “border” points shared between a set Xn and a set Lme. No two Axis countries share the same points. It follows that for the correspondent’s testimony to be true, K3,3 must be a planar graph with no intersecting edges.
Proof that K3,3 is not a planar graph
We aim to prove by contradiction that K3,3 is not a planar graph. Assume that K3,3 is a planar graph, then Euler’s polyhedral formula holds: |V|-|E|+|F|=2. As the number of vertices |V|=6 and the number of edges |E|=9 in this case, we obtain |F|=2-6+9=5.
As there are no loops and two edges connecting the same pair of points, there cannot be a face with only one or two edges. As no two points on the same side are connected, there are also no closed paths that can be achieved by just three edges, as points that are two edges away from each other are always at the same side of the bipartite graph. However, a closed path l1→x2→l2→x1→l1 of 4 edges can be found in the graph. Hence, a face in the graph can only be inscribed by 4 or more edges.
We have determined that |F|=5. Then the sum of the edges of each face can only be equal to or greater than 5×4=20. As each edge can be shared by a maximum of two faces, the number of edges |E|≤20/2=10, with |E|=10 being the case in which all edges are shared.
However, we have already established that |E|=9. We have arrived at the contradiction by assuming that K3,3 is planar graph. Hence, K3,3 is not planar. By our earlier model, it implies that it is not possible for every Allied country on Flatplanet to be exactly 1fkm away from every Axis country, and that our correspondent’s testimony is false.
Another proof that K3,3 is not a planar graph
This should be much less painful to follow. You can ignore the previous section now
□!
(24 Mar 2013, Dorigny in the Switz)
