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.
