13 Three applications of Euler’s formula

Theorem 13.1 Euler’s formula

If \(G\) is a connected plane graph with \(n\) vertices, \(e\) edges and \(f\) faces, then

\[ n - e + f = 2. \]

Proof ▶

TODO

Proposition 13.2

Let \(G\) be any simple plane graph with \(n{\gt}2\) vertices. Then \(G\) has at most \(3*n - 6\) edges.

Proof ▶

TODO

Proposition 13.3

Let \(G\) be any simple plane graph with \(n{\gt}2\) vertices. Then \(G\) has a vertex of degree at most \(5\).

Proof ▶

TODO

Proposition 13.4

Let \(G\) be any simple plane graph with \(n{\gt}2\) vertices. If the edges of \(G\) are two-colored, then there is a vertex of \(G\) with at most two color-changes in the cyclic order of the edges around the vertex.

Proof ▶

TODO

Theorem 13.5 Sylvester-Gallai

Given any set of \(n \ge 3\) points in the plane, not all on one line, there is always a line that contains exactly two of the points.

Proof ▶

TODO

Theorem 13.6 Monochromatic lines

Given any finite configuration of “black” and “white” points in the plane, not all on one line, there is always a “monochromatic” line: a line that contains at least two points of one color and none of the other.

Proof ▶

TODO

Lemma 13.7

Every elementary triangle \(\Delta = \operatorname{conv}\{ p_0, p_1, p_2\} \subset \mathbb {R}^2\) has area \(A(\Delta )=12\)

Proof ▶

TODO

Theorem 13.8 Pick’s theorem

The area of any (not necessarily convex) polygon \(Q\subset \mathbb {R}^2\) with integral vertices is given by

\[ A(Q) = n_{int} + \frac{1}{2}n_{bd} - 1 \]

where \(n_{int}\) and \(n_{bd}\) are the numbers of integral points in the interior respectively on the boundary of \(Q\).

Proof ▶

TODO