Q11 Matemática (Hungary-Israel Binational 2001)
Aqui denota um grafo simples não direcionado com vértices, denota o grafo completo com vértices, o grafo bipartido completo cujos componentes têm e vértices, e um circuito com vértices. O número de arestas no grafo é denotado por . (a) Seja um primo. Considere o grafo cujos vértices são os pares ordenados com e cujas arestas unem os vértices e se e somente se . Prove que este gráfico não contém . (b) Prove que para infinitos valores existe um gráfico com que não contém .