(POSCOMP 2014 questão 36). Considerando que um grafo possui n vértices e m arestas, assinale a alternativa que apresenta, corretamente, um grafo pl...

Para determinar se um grafo é planar, podemos usar a fórmula de Euler, que relaciona o número de vértices (n), o número de arestas (m) e o número de faces (f) de um grafo planar. A fórmula é dada por: n - m + f = 2. Podemos verificar cada uma das alternativas para ver qual delas satisfaz a fórmula de Euler: a. n = 5, m = 10 5 - 10 + f = 2 -5 + f = 2 f = 7 b. n = 6, m = 15 6 - 15 + f = 2 -9 + f = 2 f = 11 c. n = 8, m = 12 8 - 12 + f = 2 -4 + f = 2 f = 6 d. n = 9, m = 22 9 - 22 + f = 2 -13 + f = 2 f = 15 e. n = 7, m = 21 7 - 21 + f = 2 -14 + f = 2 f = 16 A única alternativa que satisfaz a fórmula de Euler (n - m + f = 2) é a alternativa c. Portanto, a resposta correta é a alternativa c) n = 8, m = 12.