Desenhe dois grafos não orientados, não isomorfos, com quatro vértices e quatro arestas cada. Explique como você sabe que eles não são isomorfos.

Passo 1

O enunciado pede dois grafos simples, não orientados, cada um com quatro vértices e quatro arestas, de modo que eles não sejam isomorfos. Vamos usar o conceito de sequência de graus (degree sequence) para mostrar a não isomorfia: grafos isomorfos têm necessariamente a mesma sequência de graus.

Passo 2

Escolhemos os seguintes grafos em termos de lista de arestas sobre o conjunto de vértices v1,v2,v3,v4:
Grafo G:
E(G)=v1,v2,,v2,v3,,v3,v4,,v4,v1
Este é o ciclo quadrado C4, em que cada vértice tem grau 2.
Grafo H:
E(H)=v1,v2,,v2,v3,,v3,v1,,v1,v4
Aqui temos um triângulo v1,v2,v3 mais uma aresta pendente v1,v4.

Passo 3

Calculamos a sequência de graus de cada grafo:
Para G (o ciclo C4):
deg(v1)=deg(v2)=deg(v3)=deg(v4)=2,
logo a sequência de graus de G é ,(2,2,2,2).
Para H:
deg(v1)=3, deg(v2)=2, deg(v3)=2, deg(v4)=1,
logo a sequência de graus de H é ,(3,2,2,1).
Como as sequências de graus são diferentes, não existe bijeção de vértices que preserve adjacências de um grafo no outro. Portanto, G e H não são isomorfos.

Resposta

Grafo G: ciclo C4 com arestas v1,v2,v2,v3,v3,v4,v4,v1.
Grafo H: triângulo v1,v2,v2,v3,v3,v1 mais aresta pendente v1,v4.
Eles não são isomorfos pois as sequências de graus são (2,2,2,2) em G e (3,2,2,1) em H, claramente distintas.