%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de MAC5770 Introdução à Teoria dos Grafos               %
% 1o. semestre de 2008                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 02 Jun 2008 09:07:55pm BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%\usepackage{refcheck}
\usepackage{srcltx}

\let\:=\colon
\let\epsilon=\varepsilon
\let\phi=\varphi
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\dim{\mathop{\rm dim}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\im{\mathop{\rm im}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim
\def\comp{^{\rm c}}

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cE{\mathcal E}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}
\def\cZ{\mathcal Z}

\def\barp{{\bar p}}

\def\Ave{\mathop{{\rm Ave}}\nolimits}
\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}
\def\diam{\mathop{{\rm diam}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfa{\textbf{a}}
\def\bfb{\textbf{b}}
\def\bff{\textbf{f}}
\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}
\def\bfX{\textbf{X}}
\def\bfdelta{\boldsymbol\delta}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
%\def\datedue#1{}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\let\hint\sugestao
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC5770 Teoria dos Grafos]{%
  {\sl Exercícios}\\\medskip
  Introdução à Teoria dos Grafos\\\medskip
  1{\tiny o.} semestre de 2008}  
\date{Versão de \today}
\maketitle
\pagestyle{plain}
\footskip=25pt

\begin{enumerate}
  
\item\label{Q:1}
  \begin{enumerate}
  \item[(\textit{i})]Prove que
    \begin{multline}
      \label{eq:2}\qquad
      |A\cup B\cup C|=|A|+|B|+|C|\\-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap
       C|,
       \qquad
    \end{multline}
    para quaisquer conjuntos~$A$, $B$ e~$C$ finitos.
    
  \item[(\textit{ii})] Sejam dados conjuntos finitos~$A_1,\dots,A_n$.  Prove
    que
    \begin{equation}
      \label{eq:IEP}
      \Big|\bigcup_{1\leq i\leq n}A_i\Big|
      =\sum_{\emptyset\neq J\subset[n]}(-1)^{|J|-1}\Big|\bigcap_{j\in
      J}A_j\Big|, 
    \end{equation}
    onde~$[n]=\{1,\dots,n\}$ e a soma é sobre todos os conjuntos~$J$ não-vazios
    de~$[n]$.
  \end{enumerate}
  \datedue{11/3/2008}
  
\item Sejam~$A_i$ como na Questão~\ref{Q:1}(\textit{ii}) acima.  Prove que
  \begin{equation}
    \label{eq:3}
    \Big|\bigcup_{1\leq i\leq n}A_i\Big|\leq\sum_{1\leq j\leq n}|A_j|
  \end{equation}
  e que
  \begin{equation}
    \label{eq:1}
    \Big|\bigcup_{1\leq i\leq n}A_i\Big|
    \geq\sum_{1\leq j\leq n}|A_j|-\sum_{1\leq k<\ell\leq n}|A_k\cap A_\ell|.
  \end{equation}
  
\item Quantas partições tem um conjunto com~$n$ elementos?  Dê as melhores
  estimativas superiores e inferiores que você conseguir.
  
\item\label{Q:Bool} Para cada natural~$n$, seja~$P_n$ a ordem parcial cujos
  elementos são as partes de~$[n]=\{1,\dots,n\}$ e a relação de ordem é a
  inclusão.  Desenhe o diagrama de Hasse das ordens parciais~$P_0$, $P_1$,
  $P_2$, $P_3$ e~$P_4$.  \datedue{13/3/2008}
  
\item Para naturais~$a\leq b$, seja~$D(a,b)$ a ordem parcial sobre os
  elementos~$\{x\in\NN\:a\leq x\leq b\}$, com a relação de ordem~$\preceq$
  dada por~$x\preceq y$ se e só se~$x$ divide~$y$.
  \begin{itemize}
  \item[(\textit{i})]Desenhe o diagrama de Hasse de~$D(3,15)$.

  \item[(\textit{ii})]Quais são os elementos maximais de~$D(3,15)$.  E os
    minimais?  A ordem~$D(3,15)$ tem um elemento máximo?  Ele tem um elemento
    mínimo? 

  \item[(\textit{iii})]Para quais valores de~$a$ e~$b$ a ordem~$D(a,b)$ tem um
    elemento mínimo?  Para quais valores~$D(a,b)$ tem um elemento máximo? 
    
  \item[(\textit{iv})]Descreva a ordem~$D(n+1,2n)$ para todo número
    natural~$n$.

  \end{itemize}
  \datedue{13/3/2008}
  
\item Uma \textit{anticadeia} em uma ordem parcial~$P$ é um subconjunto de~$P$
  cujos elementos são dois-a-dois incomparáveis.\footnote{Seja~$\preceq$ uma
    ordem sobre um conjunto~$P$.  Dizemos que~$x$ e~$y$ são
    \textit{comparáveis} (em relação a~$\preceq$) se~$x\preceq y$ ou~$y\preceq
    x$; caso nenhuma dessas duas relações valha, dizemos que~$x$ e~$y$ são
    \textit{incomparáveis}.}  Determine o tamanho máximo de uma anticadeia na
  ordem~$P_n$, definida na Questão~\ref{Q:Bool}.
  
\item São dados~$2n$ points no espaço.  Adicionamos a esta
  configuração~$n^2+1$ segmentos, conectando estes pontos, de alguma forma
  arbitrária.\footnote{Havia um erro de digitação nesta questão.  O enunciado
    agora está correto.}  Mostre, dentre os~$2n$ pontos originais, há três
  deles conectados por segmentos adicionados. \datedue{13/3/2008}
  
\item São dados~$n$ circunferências desenhadas no plano.  Estas
  circunferências dividem o plano em regiões.  Dizemos que duas dessas regiões
  são \textit{adjacentes} se eles têm uma fronteira comum (isto é, se um arco
  de circunferência separa estas regiões).  Mostre que é possível colorir
  estas regiões com duas cores, de forma que quaisquer duas regiões adjacentes
  têm cores diferentes.

\item 
  \begin{itemize}
  \item[(\textit{i})]Sejam~$r_1,\dots,r_{n-1}$ retas no plano ($n\geq1$).
    Prove que existe uma reta~$r_n$ no plano que intercepta as~$n-1$ retas
    dadas em~$n-1$ pontos distintos.
  \item[(\textit{ii})]Deduza que~$L_n\geq L_{n-1}+1$ para todo~$n>0$.  Aqui,
    como visto em sala, $L_n$~é o número máximo de regiões em que podemos
    dividir o plano com~$n$ retas.
  \end{itemize}

\item Prove a unicidade no Teorema de Zeckendorf.
  \datedue{27/3/2008}
  
\item\label{Q:g_4} Desenhe todos os grafos de ordem~$4$, a menos de
  isomorfismo.  Isto é, você deve dar a lista completa dos grafos com~$4$
  vértices, sem incluir dois grafos isomorfos (há~$11$ deles).

\item 
  \begin{enumerate}
  \item[(\textit{i})]Desenhe o grafo de Petersen.
  \item[(\textit{ii})]Seja~$H$ o grafo linha de~$K^5$, o grafo completo de
    ordem~$5$ (dessa forma, $V(H)=E(K^5)$ e~$x$ e~$y$ são adjacentes em~$H$ se
    e só se~$x\cap y\neq\emptyset$).  Quantos vértices e quantas arestas
    tem~$H$?
  \item[(\textit{iii})]Seja~$J$ o complemento de~$H$.\footnote{Assim, dois
      vértices são adjacentes em~$J$ se e só se eles não são adjacentes
      em~$H$.}  Desenhe~$J$.
  \item[(\textit{iv})]Decida se o grafo de Petersen e o grafo~$J$ são
    isomorfos.  Justifique sua resposta.
  \end{enumerate}

\item Seja~$P=(V,E)$ o grafo de Petersen.
  \begin{enumerate}
  \item[(\textit{i})]Um \textit{automorfismo} de~$P$ é simplesmente um
    isomorfismo~$\sigma\:V\to V$ de~$P$ (isto é, um homomorfismo bijetor cuja
    inversa~$\sigma^{-1}$ é também um homomorfismo).  Descreva~$5!=120$
    automorfismos de~$P$.  \datedue{27/3/2008}
  \item[(\textit{ii})] [Desafio] O grafo~$P$ tem algum \textit{outro}
    automorfismo?
  \end{enumerate}

\item 
  \begin{enumerate}
  \item[(\textit{i})]Existe um homomorfismo do grafo de Petersen~$P$
    no~$K^3$?  Justifique sua resposta.
  \item[(\textit{ii})]Existe um homomorfismo do grafo de Petersen~$P$
    no~$K^2$?  Justifique sua resposta.
  \end{enumerate}
  \datedue{27/3/2008}

\item Seja~$g_n$ o número de grafos de ordem~$n$, a menos de isomorfismo.
  Assim, temos~$g_4=11$ (veja Questão~\ref{Q:g_4}).  Prove que
  \begin{equation}
    \label{eq:4}
    {1\over n!}2^{n\choose2}\leq g_n\leq 2^{n\choose2}.
  \end{equation}
  
\item{} [Desafio] As cotas superior e inferior em~\eqref{eq:4} são bastante
  diferentes.  Você consegue melhorar alguma dessas cotas significativamente?  
  
\item Um \textit{grafo cúbico} é um grafo $3$-regular (todo vértice tem
  grau~$3$).  Decida para quais naturais~$n$ existe um grafo cúbico de
  ordem~$n$.  

\item{} [Desafio] Seja~$G$ um grafo obtido pela adição de uma aresta a um
  grafo $4$-regular.  Assim, se~$G$ tem ordem~$n$, ele tem~$2n+1$ arestas.
  Prove que~$G$ tem um subgrafo $3$-regular.

\end{enumerate} 

\bigskip
\noindent
Uma excelente fonte de exercícios para esta disciplina é o texto
\textit{Exercícios de Teoria dos Grafos}, de Paulo Feofiloff.  Veja 
$$
\verb|http://www.ime.usp.br/~pf/grafos-exercicios/|
$$
Aliás, muitos dos exercícios desta lista serão tirados de lá.
\bigskip

\begin{enumerate}\setcounter{enumi}{18}
\item Faça o exercício E$\,$2.1.6 do ETG (Exercícios de Teoria dos Grafos).
  \datedue{27/3/2008}
 
\item Seja~$G$ um grafo e sejam~$x$ e~$y$ dois vértices de~$G$.
  \begin{itemize}
  \item[(\textit{i})]Seja~$W=w_0w_1\dots w_k$ um $x$--$y$ passeio em em~$G$
    (isto é, $w_0=x$ e~$w_k=y$).  Prove que existe um $x$--$y$ caminho
    em~$G$ que usa somente of vértices que ocorrem em~$W$.
    
  \item[(\textit{ii})]Suponha que há dois $x$--$y$ caminhos (distintos) em~$G$.
    É verdade que~$G$ contém um circuito?
    
  \item[(\textit{iii})]Suponha que há duas $x$--$y$ trilhas (distintas) em~$G$.
    É verdade que~$G$ contém um circuito?
    
  \item[(\textit{iv})]Suponha que há dois $x$--$y$ passeios (distintos)
    em~$G$.  É verdade que~$G$ contém um circuito?
  \end{itemize}
  \datedue{3/4/2008}

\item Prove que todo grafo com~$\delta(G)\geq3$ tem um circuito de comprimento
  par. 

\item Prove que todo grafo conexo contém um caminho de comprimento
  $\min\{2\delta(G),|V(G)|-1\}$.

\item Seja~$G$ um grafo conexo e~$\dist\:V(G)\times V(G)\to\RR$ a função
  distância associada a~$G$.  Prove que valem as seguintes propriedades:
  \begin{itemize}
  \item[(\textit{i})]$\dist(x,y)\geq0$ para todo~$x$, $y\in V(G)$ e
    $\dist(x,y)=0$ se e só se~$x=y$.
  \item[(\textit{ii})]$\dist(x,y)=\dist(y,x)$ para todo~$x$, $y\in V(G)$. 
  \item[(\textit{iii})]$\dist(x,z)\leq\dist(x,y)+\dist(y,z)$ para todo~$x$,
    $y$ e~$z\in V(G)$.  
  \end{itemize}
  
\item Seja~$G$ um grafo.  Prove que quaisquer duas das asserções abaixo
  implica a terceira:
  \begin{itemize}
  \item[(\textit{i})]$G$ é conexo.
  \item[(\textit{ii})]$G$ é acíclico.
  \item[(\textit{iii})]$G$ tem~$|V(G)|-1$ arestas.
  \end{itemize}
  Como são conhecidos os grafos~$G$ que satisfazem duas das (e portanto todas
  as) propriedades acima?  \datedue{3/4/2008}

\item Seja~$T$ uma árvore com grau máximo~$\Delta=\Delta(T)$.  Mostre que~$T$
  tem pelo menos~$\Delta$ folhas.  \datedue{15/4/2008}
  
\item Seja~$\cF$ uma coleção de subárvores de uma árvore~$T$ com a propriedade
  de que, para quaisquer dois membros~$T'$ e~$T''$ de~$\cF$, temos~$V(T')\cap
  V(T'')\neq\emptyset$.  Mostre que existe um vértice de~$T$ que pertence a
  todas as árvores em~$\cF$.  \datedue{15/4/2008}

\item 
  \begin{enumerate}
  \item[(\textit{i})]Descreva o algoritmo de busca em profundidade em um
    grafo.  Explique como fica definida uma \textit{árvore de busca em
      profundidade} ao executarmos tal busca em um grafo conexo.
  \item[(\textit{ii})]Seja~$G$ um grafo conexo e seja~$r$ um vértice de~$G$.
    Suponha que executamos uma busca em profundidade em~$G$, a partir de~$r$.
    Seja~$T$ a árvore de busca em profundidade assim definida.  Mostre que~$T$
    é uma árvore normal com raiz~$r$.
  \end{enumerate}
  
\item Seja~$T$ uma árvore e seja~$a$ um autormorfismo de~$T$.  Mostre que ou
  (\textit{i})~existe um vértice~$x$ de~$T$ tal que~$a(x)=x$ ou
  (\textit{ii})~existe uma aresta~$\{x,y\}$ tal que~$a(\{x,y\})=\{x,y\}$.
  \datedue{22/4/2008} 
  
\item Sejam~$G$ um grafo e~$M$ um emparelhamento em~$G$.  Dizemos que um
  caminho~$P$ é um caminho \textit{$M$-alternante} se as arestas presentes
  em~$P$ pertencem a~$M$ e a~$E(G)\setminus M$, alternadamente.  Podemos
  definir \textit{circuitos $M$-alternantes} de forma análoga.  Seja agora~$N$
  um segundo emparelhamento em~$G$.  Descreva como é o subgrafo de~$G$ gerado
  pela diferença simétrica~$M\bigtriangleup N=(M\cup N)\setminus(M\cap N)$.
  
\item Sejam~$G$ um grafo e~$M$ um emparelhamento em~$G$.  Mostre que~$M$ é de
  cardinalidade máxima se e só se não existe um caminho
  \textit{$M$-aumentador} em~$G$, isto é, um caminho $M$-alternante com ambos
  os extremos não-cobertos por~$M$.  \datedue{6/5/2008}.

\def\defect{\mathop{\rm def}\nolimits}

\item Seja~$G$ um grafo bipartido com bipartição~$(A,B)$.  Para cada~$X\subset
  A$, seja~$\defect(X)=|X|-|\Gamma(X)|$.  Seja $\gamma=\max_X\defect(X)$, onde
  o máximo é tomado sobre todo~$X\subset A$.  Mostre que
  \begin{equation}
    \label{eq:5}
    \nu(G)=|A|-\gamma.
  \end{equation}
  \sugestao{Adicione uma quantiadade adequada de vértices a~$B$, e conecte-os
  a todos os vértices em~$A$.}  \datedue{6/5/2008}

\item Seja~$G$ um grafo bipartido com bipartição~$(A,B)$.  Mostre que as três
  asserções abaixo são equivalentes:
  \begin{enumerate}
  \item[(\textit{i})]$G$ é conexo e cada aresta de~$G$ pertence a um
    emparelhamento perfeito.
  \item[(\textit{ii})]$G$ não é o complemento do~$K^2$ e, para cada~$x\in A$
    e~$y\in B$, o grafo~$G-x-y$ tem um emparelhamento perfeito.
  \item[(\textit{iii})]$G$ não é o complemento do~$K^2$, $|A|=|B|$, e, para
    cada~$\emptyset\neq X\subset A$, com~$X\neq A$, temos~$|\Gamma(X)|>|X|$.
  \end{enumerate}
  Os grafos bipartidos~$G$ satisfazendo (\textit{i})--(\textit{iii}) são
  conhecidos como \textit{grafos bipartidos elementares}.  \datedue{6/5/2008}

\item Seja~$G$ um grafo bipartido com bipartição~$(A,B)$.  Suponha que~$G$ tem
  um emparelhamento perfeito e que todo vértice em~$A$ tem grau pelo
  menos~$k$.  Mostre que~$G$ tem pelo menos~$k!$ emparelhamentos perfeitos.
  \datedue{6/5/2008} 
  
\item Para cada natural~$n$, considere~$P_n$, a ordem parcial das partes
  de~$[n]$, ordenadas por inclusão.  Assim, $P_n$~tem~$2^n$ elementos e~$x\leq
  y$ se~$x\subset y$.
  \begin{enumerate}
  \item[(\textit{i})]Exiba explicitamente uma anticadeia de tamanho máximo
    em~$P_n$, para~$0\leq n\leq4$.
  \item[(\textit{ii})]Escreva~$P_n$ como uma união de cadeias, para~$0\leq
    n\leq 4$, com o número mínimo possível de cadeias em cada caso.
  \item[(\textit{iii})]Argumente cuidadosamente por que suas anticadeias
    em~(\textit{i}) são máximas e por que suas decomposições em~(\textit{ii})
    são mínimas (usam o número mínimo possível de cadeias).
  \end{enumerate}\datedue{8/5/2008} 
  
\item Encontre em~$P_n$ uma anticadeia de cardinalidade~$n\choose\lfloor
  n/2\rfloor$ e encontre uma decomposição de~$P_n$ nesse mesmo número de
  cadeias.  Deduza que o tamanho máximo de uma anticadeia em~$P_n$
  é~$n\choose\lfloor n/2\rfloor$.  \datedue{8/5/2008}

\item 
  \begin{enumerate}
  \item[(\textit{i})]Prove que todo grafo cúbico sem arestas de corte tem um
    emparelhamento perfeito.
  \item[(\textit{ii})]Decida se todo grafo cúbico tem um emparelhamento perfeito.
  \end{enumerate}
  \datedue{8/5/2008}

\item Sejam~$G$ e~$H$ dois grafos.  Defina o grafo~$G\cup H$ como sendo o
  grafo com conjunto de vértices~$V(G)\cup V(H)$ e conjunto de
  arestas~$E(G)\cup E(H)$.  Prove que~$\chi(G\cup H)\leq\chi(G)\chi(H)$.
  \datedue{20/5/2008}
  
\item Seja~$G$ um grafo com~$n$ vértices.  Suponha que exista uma partição
  $V(G)=V_1\cup\dots\cup V_k$ de~$V(G)$ tal que, para todo~$i\neq j$,
  existem~$x_i\in V_i$ e~$x_j\in V_j$ que \textit{não} são adjacentes em~$G$.
  Prove que~$\chi(G)\leq n-k+1$.  \datedue{20/5/2008}
  
\item Prove que~$\chi(G)+\chi(G\comp)\leq n+1$, onde~$G\comp$ é o complemento
  de~$G$ e~$n=|V(G)|$.  Prove também que~$\chi(G)\chi(G\comp)\geq n$.
  \datedue{20/5/2008}

\item{} [Desafio] Prove ou desprove: existe uma função~$f$ tal que, para todo
  grafo~$G$, temos~$\chi(G)\leq f(\omega(G))$.
  
\item\label{Q:41} Seja~$G$ um grafo e~$0\leq\beta\leq1$ um número real.
  Dizemos que~$G$ tem a propriedade~$P(\beta)$ se, para todo subgrafo~$H$
  de~$G$, temos que~$\alpha(H)\geq\beta|V(H)|$, onde, como de usual,
  $\alpha(H)$~é o número de independência de~$H$.  Prove que um grafo~$G$ que
  satisfaz~$P(1/2)$ é bipartido.  \datedue{27/5/2008}
  
\item{} [Desafio] Prove ou desprove: um grafo~$G$ que satisfaz~$P(1/3)$
  satisfaz~$\chi(G)\leq10^{10}$.  (Veja a Questão~\ref{Q:41}.)  Seguindo a
  mesma linha, prove ou desprove: se~$G$ satisfaz~$P({1\over2}-10^{-6})$,
  então~$\chi(G)\leq10^{10^{10}}$.
  
\item Prove que `quase todo' grafo conexo~$G$ com $n$~vértices é tal
  que~$\alpha(G)\geq n/\Delta(G)$.  Para quais~$G$ essa relação não vale?
  Encontre uma relação desse gênero que vale para todo grafo~$G$.
  \datedue{27/5/2008}

\item Determine o índice cromático do grafo completo~$K^n$, para todo valor
  de~$n$.  \datedue{27/5/2008}
  
\def\ch{\mathop{\rm ch}\nolimits}

\item Seja~$G$ um grafo.  Suponha que, para todo~$v\in V(G)$, temos um
  conjunto de \textit{cores disponíveis}~$S(v)$ para~$v$.  Queremos encontrar
  uma coloração própria dos vértices de~$G$, digamos~$f\:V(G)\to S$,
  onde~$S=\bigcup_{v\in V(G)}S(v)$, de forma que~$f(v)\in S(v)$ para
  todo~$v\in V(G)$.  Em palavras: queremos uma coloração própria dos vértices
  de~$G$ que usa, em cada vértice, uma das cores disponíveis para ele.
  Seja~$s$ o menor inteiro com a seguinte propriedade: para quaisquer
  conjuntos~$S(v)$ ($v\in V(G)$) com~$|S(v)|\geq s$ para todo~$v$, existe uma
  coloração própria~$f$ como exigido acima.  Chamamos tal~$s$ de
  \textit{número de escolha} de~$G$, e o denotamos por~$\ch(G)$.
  \begin{enumerate}
  \item[(\textit{i})] Mostre que~$\ch(G)\geq\chi(G)$.
  \item[(\textit{ii})] Decida se, para todo grafo~$G$,
    temos~$\ch(G)=\chi(G)$. 
  \end{enumerate}
  \datedue{5/6/2008}
  
\item Seja~$m$ um inteiro positivo e considere~$U=[2m-1]=\{1,\dots,2m-1\}$.
  Denotamos por~$X={U\choose m}$ o conjunto de todos os subconjuntos de
  cardinalidade~$m$ de~$U$.  Sejam~$X_0$ e~$X_1$ duas `cópias disjuntas'
  de~$X$ (podemos formalizar isso pondo~$X_0=X\times\{0\}$
  e~$X_1=X\times\{1\}$).  Considere o grafo bipartido completo~$B$ com
  conjunto de vértices~$V=X_0\cup X_1$ e com todo vértice em~$X_0$ adjacente a
  todo vértice em~$X_1$.  
  \begin{enumerate}
  \item[(\textit{i})]Prove que~$\ch(B)\geq m+1$.   
  \item[(\textit{ii})]Conclua que existem grafos bipartidos~$G$ com~$n$
    vértices satisfazendo~$\ch(G)>(1/2)\log_2n$.
  \end{enumerate}
  \datedue{5/6/2008}
  
\item{} [Desafio] Seja~$B$ um grafo bipartido, com bipartição~$V(B)=U\cup W$.
  Suponha que~$|U|=|W|=n$.  Mostre que~$\ch(B)\leq\log_2(4n)$.
  \sugestao{Sejam~$S(v)$ ($v\in V(B)$) com~$|S(v)|\geq
    s=\lfloor\log_2n\rfloor+2>\log_2n+1$.  Seja~$S=\bigcup_{v\in V(G)}S(v)$.
    Considere uma partição aleatória~$S=A\cup B$ de~$S$, escolhendo para~$A$
    um subconjunto de~$S$ sorteado uniformemente ao acaso (isto é, todos os
    subconjuntos de~$S$ têm a mesma probabilidade de serem escolhidos).
    Equivalentemente, cada elemento~$c\in S$ está em~$A$ com
    probabilidade~$1/2$, e todos esses eventos são independentes.  Use as
    cores em~$A$ para colorir os vértices em~$U$ e use as cores em~$B$ para
    colorir os vértices em~$W$.  Note que basta que, para cada~$u\in U$,
    tenhamos~$A\cap S(u)\neq\emptyset$ e que para cada~$w\in W$,
    tenhamos~$B\cap S(w)\neq\emptyset$.}
  
\item Seja~$G$ um grafo com seqüência de graus $d_1\leq d_2\leq\dots\leq d_n$
  ($n\geq3$).
  \begin{enumerate}
  \item[(\textit{i})]Mostre que se~$d_k>k$ para todo~$k<n/2$, então~$G$ é
    hamiltoniano. 
  \item[(\textit{ii})]Suponha que se~$d_k\leq k$ e~$d_l\leq l$, então
    $d_k+d_l\geq n$ ($k\neq l$).  Mostre que~$G$ é hamiltoniano.
  \end{enumerate}
  \datedue{10/6/2008}

\item Seja~$G$ um grafo $n$-regular com~$2n+1$ vértices.
  \begin{enumerate}
  \item[(\textit{i})]Mostre que~$G$ tem um circuito de comprimento pelo
    menos~$2n$. 
  \item[(\textit{ii})]Mostre que~$G$ é hamiltoniano.
  \end{enumerate}
  \datedue{10/6/2008}

\end{enumerate}

\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: