MO417 - Questão para a prova oral

Número: 2013-051

Enunciado: Em um grafo não orientado, com n vértices, determine a quantidade mínima e máxima, respectivamente, de arestas que pode haver para obtermos k componentes conexas.  Considere que não há mais de uma aresta entre dois vértices e que não há laços (um laço seria uma arestas com vértices idênticos nas extremidades).

a) n+k e n^k
b) n e (n-k)²
c) n-k e n(n-1)/2
d) n-k  e (n-k+1)(n-k)/2
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo