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

Para que um grafo seja planar, ele não pode conter subgrafos homeomórficos a K5 ou K3,3. Além disso, o número máximo de arestas em um grafo planar é dado por 3n-6, onde n é o número de vértices. No caso apresentado, n = 8 e m = 12. A alternativa correta é a letra E) Grafo com 8 vértices e 10 arestas, pois um grafo completo com 8 vértices possui 28 arestas, o que não satisfaz a condição de ser planar. Já um grafo com 8 vértices e 12 arestas pode conter subgrafos homeomórficos a K5 ou K3,3, o que também não o torna planar.