[obm-l] Quadrilateros em Grafos

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

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
=========================================================================