2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.