Q8 Matemática (Hungary-Israel Binational 2001)

08 | 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 $n \geq 5$ e $e (G_{n}) \geq \frac{n ^{2}}{4} + 2$ , prove que $G_{n}$ contém dois triângulos que compartilham exatamente um vértice .