Dê um exemplo de grafo bipartido com 8 vértices, onde todos os seus vértices têm grau 3 e, para todo par de vértices v e u, N(v) neq N(u).

Passo 1

Beleza, vamos resolver esse exercício juntos! O enunciado pede para criar um grafo bipartido com 8 vértices, onde todos os vértices têm grau 3. Além disso, para qualquer par de vértices e , os conjuntos de vizinhos e devem ser diferentes. Isso envolve conceitos de teoria dos grafos, especificamente sobre grafos bipartidos e grafos regulares. Para resolver, vamos precisar entender como dividir os vértices em dois grupos e conectar cada vértice de um grupo a exatamente três vértices do outro grupo, garantindo que os conjuntos de vizinhos sejam únicos.

Passo 2

Primeiro, vamos lembrar o que é um grafo bipartido. É um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos, digamos e , de modo que não haja arestas entre vértices do mesmo conjunto. Ou seja, todas as conexões são entre e .

Passo 3

Como temos 8 vértices e o grafo é bipartido, vamos dividir os vértices em dois conjuntos iguais: e , cada um com 4 vértices. Vamos chamar os vértices de e .

Passo 4

Agora, precisamos que todos os vértices tenham grau 3, ou seja, cada vértice em deve estar conectado a três vértices em , e vice-versa. Além disso, queremos que para qualquer par de vértices, seus conjuntos de vizinhos sejam diferentes.

Passo 5

Vamos começar conectando os vértices de aos de :
  • A1 será conectado a B1, B2, B3.
  • A2 será conectado a B1, B2, B4.
  • A3 será conectado a B1, B3, B4.
  • A4 será conectado a B2, B3, B4.

Passo 6

Vamos verificar as conexões para garantir que todos os vértices têm grau 3 e que os conjuntos de vizinhos são únicos:
  • A1: B1, B2, B3
  • A2: B1, B2, B4
  • A3: B1, B3, B4
  • A4: B2, B3, B4
Agora, vemos que cada vértice em está conectado a três vértices em , e nenhum par de vértices em compartilha exatamente o mesmo conjunto de vizinhos.

Passo 7

Da mesma forma, vamos verificar para os vértices em :
  • B1: A1, A2, A3
  • B2: A1, A2, A4
  • B3: A1, A3, A4
  • B4: A2, A3, A4
Cada vértice em também está conectado a três vértices em , e todos têm conjuntos de vizinhos únicos.

Resposta

Um exemplo de grafo bipartido com 8 vértices, todos com grau 3 e com conjuntos de vizinhos distintos para cada vértice, é o grafo com os conjuntos e e as seguintes arestas:
  • A1 está conectado a B1, B2, B3
  • A2 está conectado a B1, B2, B4
  • A3 está conectado a B1, B3, B4
  • A4 está conectado a B2, B3, B4
Esse grafo satisfaz todas as condições do enunciado.

Exercícios relacionados