\documentclass[11pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}
\usepackage{gastex}
\usepackage[usenames]{color}

\setlength{\textheight}{250mm}
\newcounter{conta}
\pagestyle{empty}
\begin{document}

\vspace*{10mm}
\noindent {\it Matem\'{a}tica Discreta}
\hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2008 \\
Professor: Newton Jos\'{e} Vieira \hfill DCC/ICEx/UFMG\\
\underline{Quarta Prova} \hfill 23/06/2008

\noindent Cada quest\~ao vale 4 pontos.

\vspace*{1mm}
\begin{enumerate}
 \item Resolva, justificando de forma bem clara:
       \begin{list}{\alph{conta})}{\usecounter{conta}}
%        \item Quantos v\'ertices tem um caminho simples de comprimento $n$?
        \item Desenhe um grafo simples, $G$, e seu complemento, $G^c$, com o menor n\'umero de v\'ertices poss\'{\i}vel,
              tais que $G$ e $G^c$ tenham o mesmo n\'umero de arestas.
        \item Para que valores de $n$ $K_n$ \'e Euleriano e para que valores de $n$ $K_n$ \'e Hamiltoniano?
%        \item Em um grafo conexo com $n$ v\'ertices, qual \'e o menor n\'umero poss\'{\i}vel de arestas?
%        \item Se um grafo simples tem 60 arestas, qual \'e o n\'umero m\'{\i}nimo de v\'ertices que ele pode ter?
       \end{list}

 \item Sobre quantidades de v\'ertices e arestas:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Quantos v\'ertices e arestas tem um grafo simples conexo regular de grau 3,
              se $E=2V-6$? ($E$ \'e o n\'umero de arestas e $V$ o n\'umero de v\'ertices.)
        \item Quantas arestas tem um grafo simples com 2 componentes conexos, um de 15 v\'ertices
              e outro com 16 v\'ertices, ambos grafos regulares, um de grau 3 e outro de grau 4?
       \end{list}

 \item Em certo grupo de 19 pessoas, sabe-se que:
       \begin{itemize}
        \item todos os irm\~aos de cada pessoa participam do grupo;
        \item cada pessoa tem pelo menos um irm\~ao;
        \item 10 pessoas t\^em um n\'umero \'{\i}mpar de irm\~aos;
        \item 9 pessoas t\^em um n\'umero par de irm\~aos.
       \end{itemize}
       Se o grupo for particionado de maneira que todos os irm\~aos, e apenas
       irm\~aos, fiquem no mesmo subgrupo, quantos subgrupos ser\~ao formados:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item no m\'{\i}nimo?
        \item no m\'aximo?
       \end{list}
       D\^e tamb\'em os tamanhos dos subgrupos em cada caso.

 \item A seguir est\'a desenhada uma constru\c{c}\~ao com quatro salas, designadas por S1 a S4,
       interconectadas por seis portas, P1 a P6.

       \mbox{\setlength{\unitlength}{1mm}
        \begin{picture}(120,36)
         \gasset{Nw=6, Nh=2, Nmr=0, fillcolor=Gray, fillgray=.9}

         \put(30,0){\framebox(60,30)}
         \node(p1)(60,30){}
         \put(30,15){\line(1,0){60}}
         \put(50,0){\line(0,1){15}}
         \put(70,0){\line(0,1){15}}
         \node(p2)(40,15){}
         \node(p3)(60,15){}
         \node(p4)(80,15){}

         \node[Nw=2, Nh=6](p5)(50,7.5){}
         \node[Nw=2, Nh=6](p6)(70,7.5){}

         \put(60,32){\makebox(0,0)[b]{\small P1}}
         \put(40,17){\makebox(0,0)[b]{\small P2}}
         \put(60,17){\makebox(0,0)[b]{\small P3}}
         \put(80,17){\makebox(0,0)[b]{\small P4}}
         \put(48,7.5){\makebox(0,0)[r]{\small P5}}
         \put(72,7.5){\makebox(0,0)[l]{\small P6}}

         \put(60,24){\makebox(0,0){S1}}
         \put(39,7.5){\makebox(0,0){S2}}
         \put(60,7.5){\makebox(0,0){S3}}
         \put(81,7.5){\makebox(0,0){S4}}
        \end{picture}
       } \\
       Determine o n\'umero m\'{\i}nimo de novas portas a instalar de forma que uma pessoa possa, ao
       chegar na constru\c{c}\~ao, passar por cada porta exatamente uma vez e sair para o exterior.
       Justifique modelando o problema por meio de grafo. Em que locais devem ser instaladas as
       novas portas (se o n\'umero m\'{\i}nimo de novas portas for maior que zero)?
\end{enumerate}
\end{document}
