Suppose five points are chosen inside an equilateral triangle with side length . Show that there is at least one pair of points whose distance apart is at most .

Let be the chromatic number of graph . Show that any graph must have at least edges.

Suppose is a graph on vertices. For an edge , let be the number of triangles containing , and be the number of triangles in .

- Show that for each pair of adjacent vertices , .
- Summing over all edges we have Show that .

Remark: This implies that a graph on n vertices with edges not only contains one triangle (as it must be by Mantelâ€™s theorem), but more than .

Given a family of subsets of , its

*intersection graph*is defined by: if and only if . Suppose that the average size of is at least , and the average size of for is at most . Show that .(

*Hint: Compute .*)[Noga Alon, 1986] Let be a set of strings of length over some alphabet . Suppose that every two strings of differ in at least coordinates. Let be a number satisfying . Show that any distinct strings of attain distinct values in at least one coordinate.

(

*Hint: Assume the opposite and count the sum of distances between the pairs of 's*.)Prove that for any positive integer , there is a number such that for any -coloring of all subsets of , , there exists non-empty disjoint sets such that , and are the same.