Re: [obm-l] Triângulos em grafos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Re: [obm-l] Triângulos em grafos

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.