Oi, pessoal: Pra quem gosta de teoria dos grafos, aqui vao alguns problemas bonitinhos:
1. Um grafo simples tem 7 vertices e 11 arestas. Prove que o grafo contem um quadrilatero (tambem chamado de 4-ciclo, ou seja, o grafo contem 4 vertices A, B, C e D e as arestas AB, BC, CD e DA); 2. Mesmo problema com 14 vertices e 29 arestas; 3. Qual o menor numero de arestas que um grafo simples com n vertices deve ter a fim de conter necessariamente um quadrilatero? Um abraco, Claudio. ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================