Using the Euler Characteristic in the plane, show that five points cannot be connected by paths that do not cross

347 Views Asked by At

Given five points in the plane, show that it is impossible to connect each pair of points by paths that do not cross.

The question was asked in the context of the Euler characteristic, so I think the answer lies in projecting the points onto the sphere via stereographic projection, then showing somehow that having lines between all of them makes $\chi(S)\neq 2$, thus a contradiction. I wasn't sure how to reach this though.

2

There are 2 best solutions below

0
On BEST ANSWER

We can see the graph on the sphere. Since every two vertices must be connected, we need $4+3+2+1=10$ edges. Since this must form a cellular subdivision of the sphere, we have $$2=\chi(S^2)=5-10+F\ ,$$ so that we need $7$ faces. However, to have $7$ faces we need at least $\frac{3}{2}7>10$ edges (since every edge touches $2$ faces, so we can count it $\frac{1}{2}$ for each face, so that we get $\frac{3}{2}$ distinct edges per face).

0
On

In order to do that, you need to draw $10$ non-crossing paths. The graph that represents is $K_5$, the complete graph on $5$ vertices, which isn't planar (this is essentially what you are trying to prove).

Using Euler's polyhedron formula $V - E + F = 2$, we get the bound that $E \leq 3V - 6$ for any planar graph, but $10 > 3\cdot 5 - 6=9$.