\documentclass[a4paper,10pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{subfigure}
\usepackage{graphicx,url}
\usepackage{geometry}
%opening
\title{Ata da Questão 5.3.4}
\author{Rafael L. Gomes}

\geometry{verbose,a4paper,tmargin=20mm,bmargin=30mm,lmargin=15mm,rmargin=15mm}

\begin{document}

\maketitle

\textbf{Enunciado:}a) Prove that $\chi(C_n;k) = (k - 1)^n +
(-1)^n(k-1)$. b) For $H=G \vee K_1$, prove that $\chi(F;k) =
k\chi(G;k-1)$. From this and part (a), find the chromatic polynomial
of the wheel $C_n \vee K_1$.

\section{Parte A}

Considerando-se somente grafos simples, no caso base para a prova
utiliza-se $n=3$, visto que com um vértice e dois vértices não se pode
ter ciclos sem utilizar \textit{loops} e múltiplos caminhos,
respectivamente.

No caso base $n=3$, a fórmula dada resulta em:
\[
 \chi(C_3;k) =
(k-1)^3-(k-1) = (k-1)[(k-1)^2-1] = (k-1)[k^2-2k] = k(k - 1)(k-2),
\]
que é realmente o polinômio cromático de $C_3 = K_3$.

Usando-se a recorrência cromática em um ciclo com $n$ vértices, para
os casos em que $n \geq 4$, pode-se gerar um caminho com o mesmo número de
vértices e um ciclo com $n-1$ vértices. Um exemplo desse processo pode
ser visualizado na Figura \ref{figura}. Note que o polinômio
cromático para um caminho com $n$ vértices é $k(k - 1)^{n-1}$.

\begin{figure}[htb]
     \centering
     \includegraphics[scale=0.5]{img.png}
     \caption{Exemplo de Recorrência Cromática em Ciclos}
     \label{figura}
\end{figure}

Temos então:
\begin{eqnarray*}
  \chi(C_n;k) &=& \chi(C_n - e;k) - \chi(C_n . e; k) \\
              &=& \chi(P_n - e;k) - \chi(C_{n-1};k).
\end{eqnarray*}

Utilizando-se a hipótese de indução para $n-1$ vértices, tem-se:
\[
  \chi(C_{n-1};k) = (k-1)^{n-1}+(-1)^{n-1}(k-1).
\]

Substituindo na equação anterior, fica:
\begin{eqnarray*}
  \chi(C_n;k) &=& \chi(P_n - e;k) - \chi(C_{n-1};k) \\
              &=& k(k-1)^{n-1} - (k-1)^{n-1} - (-1)^{n-1}(k-1) \\
              &=& (k-1)^{n} + (-1)^n(k-1),
\end{eqnarray*}
o que encerra nossa prova.

\section{Parte B}

Se $H= G \vee K_1$, então $\chi(H;k)=k\chi(G;k-1)$. Seja $x$ o vértice
adicionado em G para se obter H. Em toda coloração apropriada, a cor
usada em $x$ não pode ser utilizada em nenhum outro vértice de H. Cada
uma das $k$ maneiras de colorir $x$ combina com cada uma das
$\chi(G;k-1)$ maneiras de fazer a coloração apropriada do resto de
H. Sendo assim, $\chi(H;k) = k\chi(G;k-1)$, e particularmente tem-se
$\chi(C_n \vee K_1;k) = k(k-2)^n+(-1)^nk(k-2)$.

\end{document}
