Valdery Sousa.
_____________________________________________
Claudio Buffara <claudio.buffara@terra.com.br> wrote:
on 02.02.04 12:34, Cláudio (Prática) at claudio@praticacorretora.com.br wrote:
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.
A minha demonstracao da parte (a) eh por inducao em n:
n = 2 ==>
G tem 4 vertices e 5 arestas ==>
G eh igual a K_4 (grafo completo com 4 vertices) com uma aresta removida. Como K_4 contem 4 triangulos e cada uma de suas arestas pertence a dois deles, a remocao de uma aresta qualquer ainda deixa 2 triangulos "vivos".
Hipotese de Inducao: Qualquer grafo com 2n vertices e
n^2 + 1 arestas contem pelo menos 1 triangulo.
Seja G um grafo com 2n+2 vertices e (n+1)^2 + 1 arestas.
Sejam A e B dois vertices de G ligados por uma aresta.
Se existe um terceiro vertice de G ligado por uma aresta a A e B, entao acabou!
Caso contrario, o conjunto dos vertices ligados a A e o conjunto dos vertices ligados a B sao disjuntos. Assim, alem da aresta ligando A e B, existirao no maximo mais 2n arestas tendo A ou B como extremidade.
Seja H o subgrafo de G obtido pela remocao de A e B e de todas as arestas que tem A ou B (ou ambos) como extremidade. H terah 2n vertices e, no minimo, (n+1)^2 + 1 - (2n + 1) = n^2 + 1 arestas. Pela hipotese de inducao, H (e, portanto, G) deverah conter um triangulo.
****
Imagino que a parte (b) tambem saia por inducao. Pelo menos a base (n=2) eh a mesma...
Um abraco,
Claudio.