Q10 Matemática  (Hungary-Israel Binational 2001)

Aqui $G_n$ denota um grafo simples não direcionado com $n$ vértices, $K_n$ denota o grafo completo com $n$ vértices, $K_{n,m}$ o grafo bipartido completo cujos componentes têm $m$ e $n$ vértices, e $C_n$ um circuito com $n$ vértices. O número de arestas no grafo $G_n$ é denotado por $e(G_n)$. (a) Se $G_n$ não contém $K_{2,3}$ , prove que $e(G_n)\le \frac{n\sqrt{n}}{\sqrt{2}}+n$. (b) Dados $n\ge 16$ pontos distintos $P_1,...,P_n$ no plano, prove que no máximo $n\sqrt{n}$ dos segmentos $P_i{P}_j$ têm comprimento unitário.