Seja G um gráfico com grau máximo 3

Question

Prove que seus vértices podem ser coloridos por 2 cores (cada vértice recebe uma cor) de forma que não haja nenhum caminho de comprimento dois cujos 3 vértices tenham a mesma cor.

Answer 1

A afirmação é verdadeira mesmo para gráficos infinitos. É o suficiente para provar isso para gráficos finitos; o caso infinito pode ser derivado do caso finito imitando qualquer uma das provas do teorema de De Bruijn – Erdős .

Deixei $G$seja um gráfico finito. Entre todas as colorações do vértice de$G$com duas cores, azul e vermelho, escolha uma que minimize o número de "arestas ruins", ou seja, arestas que unem dois vértices da mesma cor. Eu afirmo que essa coloração faz o que você quiser.

Suponha, como contradição, que haja um caminho de comprimento dois cujas bordas são todas da mesma cor, digamos, azul. Em outras palavras, existe um vértice azul$v$que tem (pelo menos) dois vizinhos azuis, e no máximo um vizinho vermelho. Se mudarmos a cor de$v$do azul para o vermelho, perdemos pelo menos duas bordas ruins, enquanto adquirimos no máximo uma nova borda ruim. Assim, a nova coloração terá menos bordas ruins do que antes, contradizendo o fato de que a coloração original minimizou o número de bordas ruins.

Answer 2

Forte indução no número de vértices $n$. A afirmação é verdadeira quando$n = 1, 2, 3$.

Deixei $G$ ter $n$ vértices e assumir que a afirmação é verdadeira para gráficos com $k$ vértices para $k<n$. Agora você pode assumir$G$ está conectado como quando não está conectado, cada componente tem um número estritamente menor de vértices e você pode colori-los apropriadamente.

E se $G$ tem um vértice $v$ de grau $1$, em seguida, exclua-o, cor $G\setminus\{v\}$adequadamente. Deixei$w$ seja o vizinho de $v$, dê $v$ a cor diferente daquela de $w$ e você está pronto para ir.

Se não, então cada vértice tem grau pelo menos 2, portanto $G$ tem um ciclo $C$. Pinte os vértices de$C$ alternadamente para que $C$ não tem um caminho de comprimento $2$ com todos os vértices tendo a mesma cor.

Remover $C$, e colorir os componentes de $G\setminus C$. Agora, enquanto se junta$C$ de volta, suponha um vértice $v\in C$ está conectado a um vértice $w$ no componente $K$, e essa $v$é de cor vermelha. Troque as cores de$K$ (então o vermelho se torna azul e o azul se torna vermelho) se necessário para que $w$ é colorido de azul e, em seguida, junte-o a $v$. Dessa forma, não há "caminho ruim" em$K$ e não pode haver nenhum caminho ruim envolvendo dois vértices (incluindo $v$) a partir de $C$ e um de $K$ ou dois vértices de $K$ e $v$. Assim,$G$ não tem "caminho ruim".

EDIT: Parece haver um erro, pois não usei o fato de que o grau máximo é 3 . De qualquer forma, verifique o gráfico, duas cores, sem comprimento de caminho 3

Você precisa de condição de grau máximo 3, pois só então um $v\in C$ estar conectado a no máximo um outro vértice e todo o negócio de troca funciona.