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
:
Grafo
:
Este é o ciclo quadrado
, em que cada vértice tem grau 2.
Grafo
:
Aqui temos um triângulo
mais uma aresta pendente
.
Passo 3
Calculamos a sequência de graus de cada grafo:
Para
(o ciclo
):
logo a sequência de graus de
é
.
Para
:
logo a sequência de graus de
é
.
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,
e
não são isomorfos.
Resposta
Grafo
: ciclo
com arestas
.
Grafo : triângulo
mais aresta pendente
.
Eles não são isomorfos pois as sequências de graus são em
e
em
, claramente distintas.
Grafo
Eles não são isomorfos pois as sequências de graus são