Q11 Matemática (Hungary-Israel Binational 2001)

11 | Hungary-Israel Binational | 2001 | Matemática

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) Seja $p$ um primo. Considere o grafo cujos vértices são os pares ordenados $(x, y)$ com $x, y \in {0, 1, ..., p - 1}$ e cujas arestas unem os vértices $(x, y)$ e $(x^{'}, y^{'})$ se e somente se $x x^{'} + y y^{'} \equiv 1 (mod p)$ . Prove que este gráfico não contém $C_{4}$ . (b) Prove que para infinitos valores $n$ existe um gráfico $G_{n}$ com $e (G_{n}) \geq \frac{n n}{2} - n$ que não contém $C_{4}$ .