Q9 Matemática (Hungary-Israel Binational 2001)

09 | 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})$ . Se $e (G_{n}) \geq \frac{n n}{2} + \frac{n}{4}$ , prove que $G_{n}$ contém $C_{4}$ .