• Matéria: Matemática
  • Autor: 708201561
  • Perguntado 3 anos atrás

Mostra: se G é regular de grau k, então L(G) é regular de grau 2k – 2.

Respostas

respondido por: silvapgs50
0

Temos que, o grafo adjunto de G será regular de grau 2k - 2, pois, cada vértice de L(G) terá grau 2k - 2.

Teoria dos grafos

Temos que, G é um grafo regular de grau k, portanto, todos os vértices de G possui uma quantidade k de arestas.

O grafo adjunto ou grafo linha de G, o qual é denotado por L(G), é obtido de G transformando cada aresta em vértice e ligando os vértices em L(G) se as arestas originais de G possuem um vértice em comum.

Seja ab uma aresta em G, temos que, o vértice a possui k - 1 arestas diferentes de ab e que b possui k - 1 arestas diferentes de ab, portanto, o grau do vértice correspondente em L(G) será:

k - 1 + k - 1 = 2k - 2

Para mais informações sobre grafos, acesse: https://brainly.com.br/tarefa/43635169

#SPJ1

Anexos:
Perguntas similares