Considere um grafo simples G com n vértices. Qual é a máxima quantidade de arestas que pode existir em G? a) n-1 b) n(n-1)/2 c) n(n+1)/2 d) n^2

Para determinar a máxima quantidade de arestas que pode existir em um grafo simples com \( n \) vértices, precisamos considerar que em um grafo simples não há laços (arestas que conectam um vértice a ele mesmo) e não há arestas múltiplas (duas arestas ligando os mesmos dois vértices). A máxima quantidade de arestas ocorre quando cada vértice está conectado a todos os outros vértices. Para um grafo com \( n \) vértices, cada vértice pode se conectar a \( n-1 \) outros vértices. No entanto, cada aresta é contada duas vezes (uma vez para cada vértice que a compõe), então a fórmula correta para a quantidade máxima de arestas é: \[ \frac{n(n-1)}{2} \] Agora, analisando as alternativas: a) \( n-1 \) - Esta é a quantidade mínima de arestas em um grafo conectado com \( n \) vértices (uma árvore). b) \( \frac{n(n-1)}{2} \) - Esta é a quantidade máxima de arestas em um grafo simples. c) \( \frac{n(n+1)}{2} \) - Esta fórmula não se aplica a grafos simples. d) \( n^2 \) - Esta quantidade considera laços e arestas múltiplas, não se aplica a grafos simples. Portanto, a alternativa correta é: b) \( \frac{n(n-1)}{2} \).