I heard of this interesting classical result from here.
Sylvester-Gallai theorem says that given a finite number of points in Euclidean plane, either all the points lie on a single line or there is a line that contains exactly two of the points.
According to Wiki it's been open for almost 50 years, from 1893 to 1941, and Erdos once asked for its answer!
My favorite proof is this. Purely Euclidean, very few objects involved, and just a few steps once you get the starting point right...Another Euclidean proof is here.
Now, surprisingly this result goes beyond Euclidean plane. My proof below is almost identical to this and doesn't require lines to be straight etc.
Proof:
Suppose there are $n$ lines, and all intersections are incident to at least $3$ lines. Also not all lines intersect at the same point. Consider the planar graph formed by intersections (vertices), line segments (edges), and regions (faces). Some edges and faces are unbounded.
If we count the edges from vertices, we get
$$
E\ge 3V+n.
$$
This is because $2E\ge\sum_{i=1}^V2d_i+2n$ where $d_i\ge 3$ is the number of lines incident to vertex $i$ and the $2n$ term comes from two unbounded intervals at the ends of each line.
Now we count the edges from faces. There are exactly $2n$ unbounded faces, moreover a neat observation is that at most $n$ of them touch two edges and the rest touch three or more edges. Every bounded face touches at least three edges. So
$$
2E\ge 3(F-n)+2n=3F-n.
$$
Adding the two inequalities we get
$$
3E\ge 3F+3V
$$
contradicting the Euler characteristic
$$
V+F-E=1.
$$
Q.E.D.
Monday, June 17, 2019
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment