Formal Book

11 Lines in the plane and decompositions of graphs

Theorem 11.1

In any configuration of \(n\) points in the plane, not all on a line, there is a line which contains exactly two of the points.

Proof

TODO

Theorem 11.2

Let \(P\) be a set of \(n\ge 3\) points in the plane, not all on a line. Then the set \(\mathcal{L}\) of lines passing through at least two points contains at least \(n\) lines.

Proof

TODO

Theorem 11.3

Let \(X\) be a set of \(n\ge 3\) elements, and let \(A_1, \dots , A_m\) be proper subsets of \(X\), such that every pair of elements of \(X\) is contained in precisely one set \(A_i\). Then \(m\ge n\) holds.

Proof

TODO

Theorem 11.4

If \(K_n\) is decomposed into complete bipartite subgraphs \(H_1, \dots , H_m\), then \(m \ge n - 1\).

Proof

TODO