|
Oi, pessoal:
Aqui vai um probleminha que, se não me engano, foi inventado pelo
Erdos:
Seja n um inteiro >= 2. Um grafo simples (sem "loops" e com no máximo
uma aresta ligando dois vértices quaisquer) tem 2n vértices e n^2+1 arestas.
a) Prove que este grafo contém um triângulo (três vértices sendo que cada
dois dos quais são ligados por uma aresta)
b) Prove que o grafo contém no mínimo n triângulos.
(para as definições relativas a grafos veja os artigos do Shine ou do Paulo
César nas Eurekas)
Um abraço,
Claudio.
|