Planar Graphs, Sylvester's Problem

Sylvester's Problem

Sylvester's problem is an interesting and unexpected application of Euler's formula. If F is a finite set of points in the plane, such that every line which passes through two points of F also passes through at least three, then the points of F are colinear.

This problem has an equivalent dual whose construction illustrates the proof. If G is a finite set of lines in the plane, such that every intersection point of two lines in G is an intersection point of at least three, then the lines of G all intersect at a point.

To show equivalence, think of the plane as the plane z = 1 in 3 space. Given a point in F, not on the z axis, draw a line to the origin and construct a plane through the origin perpendicular to this line. The intersection of this plane with z = 1 produces a line in G. Conversely, every line in G that does not pass through the z axis determines a point in F. Collinearity for a set of points in F is equivalent to the corresponding lines in G meeting at a point. So we will look at the lines in G.

For each line in G, consider the great circle determined by the corresponding plane as it cuts through the unit sphere. These divide the sphere into polygons, or faces. If not all lines of G meet in a single point, then each face has at least three sides, and we have a traditional graph embedded in the sphere. Since at least three lines cross at every vertex, the degree of every vertex is at least 6, which is impossible. Thus all lines in G intersect in a point, and the points in F are colinear.