\documentclass[12pt,a4paper]{article}

\usepackage[portuguese]{babel}
\usepackage{fullpage}

\newcounter{conta}
\begin{document}
 
\noindent Departamento de Ci\^{e}ncia da Computa\c{c}\~{a}o \hfill ICEx/UFMG \\
{\it Matem\'{a}tica Discreta} \hfill $\mbox{1}^{\mbox{\underline{o}}}$ semestre de 2005 \\
Professor: Newton Jos\'{e} Vieira \\
\underline{Quarta Lista de Exerc\'{\i}cios} \hfill Entrega: 21/06/2005.

\vspace*{4mm}
\noindent{\bf Introdu\c{c}\~{a}o \`{a} Teoria dos Grafos}
 
\begin{enumerate}
 \item {\footnotesize Quantas arestas t\^em $K_{m,m}^c$ e $K_n^c$?}

       {\it Solu\c{c}\~{a}o\/}: $K_{m,m}^c$ tem $2\times C(m,2)=m(m-1)$
       arestas. $K_n^c=$ \'e o grafo nulo e, portanto, n\~ao tem arestas.

 \item {\footnotesize Uma mulher deve transportar um le\~{a}o, uma raposa e um coelho de uma margem
       a outra de um rio, em um barco que s\'{o} cabe a mulher e mais um dos
       animais. Se o le\~{a}o e a raposa, ou a raposa e o coelho, ficarem na margem
       oposta em que estiver a mulher, em dado instante, o primeiro come o
       segundo. Este problema pode ser modelado via grafos, criando-se um
       v\'{e}rtice para cada configura\c{c}\~{a}o segura (aquela em que ningu\'{e}m come
       ningu\'{e}m) poss\'{\i}vel, e uma aresta entre dois v\'{e}rtices se a configura\c{c}\~{a}o
       representada por um puder ser obtida daquela representada pelo outro
       cruzando-se o rio. Assim feito, um caminho simples do v\'{e}rtice inicial
       (que representa todos na margem A) ao v\'{e}rtice meta (todos na outra
       margem) corresponde a uma forma de cruzar o rio com os ditos elementos.
       Construa o grafo, e mostre todas as formas de cruzar o rio com
       seguran\c{c}a para a raposa e o coelho.}

       {\it Solu\c{c}\~{a}o\/}:

       Cada v\'ertice ter\'a a forma $\langle x\rangle$, onde $x$ \'e uma
       seq\"u\^encia de s\'{\i}mbolos do conjunto $\{M,L,R,C\}$, representando os
       animais que est\~ao na margem A ($M$: mulher, $L$: le\~ao, $R$:
       raposa, $C$: coelho). Existir\'a uma aresta $\{\langle x\rangle,\langle
       y\rangle\}$, caso a situa\c c\~ao representada por $y$ possa ser obtida
       a partir daquela representada por $x$. As arestas n\~ao s\~ao
       direcionadas, representando o fato de que se $y$ pode ser obtido a partir
       de $x$, $x$ pode ser obtido a partir $y$ (como pode ser facilmente
       verificado). Com isto, o grafo ter\'a as seguintes arestas:
       
       \begin{tabular}{llll}
        $\{\langle M,L,R,C\rangle,\langle L,C\rangle\}$, &
        $\{\langle L,C\rangle,\langle M,L,C\rangle\}$, &
        $\{\langle M,L,C\rangle,\langle C\rangle\}$, &
        $\{\langle M,L,C\rangle,\langle L\rangle\}$, \\
        $\{\langle C\rangle,\langle M,R,C\rangle\}$, &
        $\{\langle L\rangle,\langle M,L,R\rangle\}$, &
        $\{\langle M,R,C\rangle,\langle R\rangle\}$, &
        $\{\langle M,L,R\rangle,\langle R\rangle\}$, \\
        $\{\langle R\rangle,\langle M,R\rangle\}$, &
        $\{\langle M,R\rangle,\langle \rangle\}$. 
       \end{tabular}
       
       Existem dois caminhos mais curtos que representam formas de cruzar o rio
       sem perdas:
       \begin{itemize}
        \item $\langle M,L,R,C\rangle \langle L,C\rangle \langle M,L,C\rangle
              \langle C\rangle \langle M,R,C\rangle \langle R\rangle
              \langle M,R\rangle \langle \rangle$
        \item $\langle M,L,R,C\rangle \langle L,C\rangle \langle M,L,C\rangle
              \langle L\rangle \langle M,L,R\rangle \langle R\rangle
              \langle M,R\rangle \langle \rangle$
       \end{itemize}

 \item {\footnotesize Um conjunto de v\'{e}rtices de um grafo \'{e} dito {\it dominante\/}, se todo
       v\'{e}rtice que n\~{a}o esteja no conjunto \'{e} adjacente a algum v\'{e}rtice do
       conjunto. Um conjunto {\it dominante minimal\/} \'{e} um conjunto dominante
       que n\~{a}o tem nenhum subconjunto pr\'{o}prio que seja conjunto dominante.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Encontre conjuntos dominantes minimais para $K_n$ e $K_{n,n}$.
        \item Encontre conjuntos dominantes minimais de tamanhos diferentes para
              o grafo:
              \begin{center}
              \begin{picture}(160,150)
               \put(50,20){\circle*{5}}
               \put(40,10){\makebox(0,0){d}}
               \put(50,20){\line(1,0){60}}
               \put(110,20){\circle*{5}}
               \put(120,10){\makebox(0,0){c}}
               \put(110,20){\line(1,2){30}}
               
               \put(140,80){\circle*{5}}
               \put(150,80){\makebox(0,0){b}}
               \put(140,80){\line(-1,1){60}}
               
               \put(80,140){\circle*{5}}
               \put(80,150){\makebox(0,0){a}}
               \put(80,140){\line(-1,-1){60}}
               
               \put(20,80){\circle*{5}}
               \put(10,80){\makebox(0,0){e}}
               \put(20,80){\line(1,-2){30}}
               \put(20,80){\line(1,0){120}}
               \put(60,80){\circle*{5}}
               \put(50,90){\makebox(0,0){f}}
               \put(60,80){\line(1,3){20}}
               \put(100,80){\circle*{5}}
               \put(110,90){\makebox(0,0){g}}
               \put(100,80){\line(-1,3){20}}
               
               \put(80,50){\circle*{5}}
               \put(90,50){\makebox(0,0){h}}
               \put(50,20){\line(1,1){30}}
               \put(110,20){\line(-1,1){30}}
               \put(80,50){\line(-2,3){20}}
               \put(80,50){\line(2,3){20}}
              \end{picture}
              \end{center}
        \item Uma rainha {\it domina\/} uma posi\c{c}\~{a}o em um tabuleiro de xadrez se
              est\'{a} na mesma linha, coluna ou diagonal da posi\c{c}\~{a}o. Descreva um
              modelo em grafo para o problema de determinar o n\'{u}mero m\'{\i}nimo de
              rainhas necess\'{a}rio para dominar todas as posi\c{c}\~{o}es do tabuleiro.
       \end{list}}

       {\it Solu\c{c}\~{a}o\/}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um conjunto unit\'ario com qualquer um dos v\'ertices de $K_n$ \'e
              conjunto dominante minimal, pois todo v\'ertice de $K_n$ \'e
              adjacente a qualquer outro. Cada um dos dois conjuntos de
              $K_{n,n}$ sem v\'ertices adjacentes \'e conjunto dominante minimal,
              pois, al\'em de n\~ao terem v\'ertices adjacentes, seus v\'ertices
              s\~ao adjacentes a todos os do outro conjunto.
        \item Exemplos de conjuntos dominantes minimais de tamanhos diferentes
              para o grafo desenhado acima: $\{a,c\}$ e $\{b,d,f\}$
        \item O problema de determinar o n\'{u}mero m\'{\i}nimo de rainhas
              necess\'{a}rio para dominar todas as posi\c{c}\~{o}es do tabuleiro
              pode ser modelado em grafos da seguintes forma:
              \begin{enumerate}
               \item[.] cada casa do tabuleiro \'e representada por um v\'ertice;
               \item[.] existe uma aresta $\{u,v\}$ se, e somente se, as casas
                        representadas por $u$ e $v$ est\~{a}o na mesma linha,
                        coluna ou diagonal.
              \end{enumerate}
              Desta forma, o n\'{u}mero m\'{\i}nimo de rainhas necess\'{a}rio para
              dominar todas as posi\c{c}\~{o}es do tabuleiro ser\'a o tamanho do
              menor conjunto dominante minimal (ou de um dos menores, se houver mais
              de um).
       \end{list}        

 \item {\footnotesize Quantos subgrafos tem $K_n$?}

       {\it Solu\c{c}\~{a}o\/}: Existem \[\sum_{k=0}^n[C(n,k)\times 2^{C(k,2)}]\] subgrafos
       de $K_n$.

 \item {\footnotesize Prove que um grafo simples com $n$ v\'{e}rtices n\~{a}o pode ser bipartite se
       tiver mais de $n^2/4$ v\'{e}rtices. (Sugest\~{a}o: Suponha que pode ser. Ent\~{a}o
       os v\'{e}rtices podem ser divididos em conjuntos de $k$ e $n-k$ v\'{e}rtices.
       Conte o n\'{u}mero de arestas.)}

       {\it Solu\c{c}\~{a}o\/}:

       Suponha que o grafo \'e bipartite. Ent\~{a}o seus v\'{e}rtices podem ser
       divididos em dois conjuntos de $k$ e $n-k$ v\'{e}rtices, de tal forma
       que v\'ertices do mesmo conjunto n\~ao s\~ao adjacentes. Neste caso, o
       n\'umero m\'aximo de arestas \'e $k\times (n-k)$ (o grafo seria
       do tipo $K_{k,n-k}$). O valor de $k$ para o qual $k\times (n-k)$  atinge o
       m\'aximo \'e dado por $d(k\times (n-k))/dk=0$, ou seja, por
       $d(nk-k^2))/dk=0$, ou ainda, $n-2k=0$, o que d\'a $k=n/2$. Assim, o
       n\'umero m\'aximo de arestas \'e $(n/2)\times (n/2)=n^2/4$! Assim, tendo
       o grafo mais de $n^2/4$ arestas, ele n\~ao pode ser bipartite.    

 \item {\footnotesize Prove que se $G$ \'e um grafo simples, ent\~ao $G$ ou $G^c$ \'e conexo.}

       {\it Solu\c{c}\~{a}o\/}: Seja $G$ um grafo simples. Suponha que $G$ n\~ao
       \'e conexo. Sejam $C_1$, $C_2$, \ldots, $C_n$ os componentes conexos de $G$
       ($n\geq 2$). Sejam $v_1$ e $v_2$ dois v\'ertices quaisquer de $G$ (e, portanto,
       de $G_c$). Se $v_1\in C_i$ e $v_2\in C_j$ para $i\not=j$, ent\~ao $\{v_1,v_2\}$
       \'e uma aresta de $G^c$. No outro caso, isto \'e, se $v_1,v_2\in C_i$
       para algum $i$, ent\~ao para qualquer v\'ertice $v$ de qualquer componente
       $C_j$, onde $j\not=i$, $\{v_1,v\}$ e $\{v,v_2\}$ s\~ao arestas de $G^c$.
       Logo, para quaisquer v\'ertices distintos $v_1$ e $v_2$ de $G^c$ existe
       caminho (de tamanho 1 ou 2) de $v_1$ a $v_2$. Portanto, se $G$ n\~ao \'e
       conexo, $G^c$ \'e conexo. Assim, $G$ ou $G^c$ \'e conexo.

 \item {\footnotesize Um v\'{e}rtice $v$ \'{e} dito ser uma {\it articula\c{c}\~{a}o\/} em $G$ quando sua
       remo\c{c}\~{a}o desconecta $G$. Prove que $v$ \'{e} uma articula\c{c}\~{a}o se, e somente se,
       existem v\'{e}rtices $u$ e $w$ tais que $v$ est\'{a} em todo caminho simples
       entre $u$ e $w$ em $G$.}

       {\it Solu\c{c}\~{a}o\/}:

       Observe, inicialmente, que se $u$ e $w$ s\~ao v\'{e}rtices tais que $v$
       est\'{a} em todo caminho simples entre $u$ e $w$, ent\~ao se $v$ for
       removido, n\~ao existir\'a mais caminho entre $u$ e $w$. Portanto,
       neste caso, $v$ \'{e} uma articula\c{c}\~{a}o. Basta mostrar, ent\~ao,
       que: se para quaisquer v\'{e}rtices $u$ e $w$ algum caminho simples
       entre $u$ e $w$ em $G$ (se existir) n\~ao cont\'em $v$, ent\~ao $v$ n\~ao
       \'{e} uma articula\c{c}\~{a}o em $G$. Mas isto tamb\'em \'e \'obvio, pois
       a remo\c c\~ao de $v$ n\~ao ir\'a inibir a exist\^encia de caminho entre
       $u$ e $w$, para quaisquer v\'ertices $u$ e $w$, caminhos estes que n\~ao
       cont\^em $v$.
       
 \item {\footnotesize Uma {\it ponte\/} em $G$ \'{e} uma aresta cuja remo\c{c}\~{a}o desconecta
       $G$. Prove que $e$ \'{e} uma ponte em $G$ se, e somente se, existem dois
       v\'{e}rtices $u$ e $v$ tais que todos os caminhos simples entre $u$ e $v$
       cont\^{e}m $e$.}

       {\it Solu\c{c}\~{a}o\/}:

       Similar \`a da quest\~ao anterior.

 \item {\footnotesize Qual \'{e} o maior n\'{u}mero poss\'{\i}vel de arestas em um grafo com 31 v\'{e}rtices, se
       cada v\'{e}rtice tem grau, no m\'{a}ximo, igual a 3?}

       {\it Solu\c{c}\~{a}o\/}:

       Sabe-se que $\sum_{v\in {\bf V}}\mbox{\it grau\/}(v)=2E$. Como o n\'umero de
       v\'ertices de grau \'{\i}mpar \'e par, para satisfazer as condi\c c\~oes
       do problema, basta ter $\sum_{v\in {\bf V}}\mbox{\it grau\/}(v)=30\times 3+2=
       92$. Assim, tem-se que o n\'umero m\'aximo de arestas \'e $E=96/2=46$.

 \item {\footnotesize Qual \'{e} o maior n\'{u}mero poss\'{\i}vel de v\'{e}rtices em um grafo com 20 arestas, se
       cada v\'{e}rtice tem grau, no m\'{\i}nimo, igual a 4?}

       {\it Solu\c{c}\~{a}o\/}:

       $\sum_{v\in {\bf V}}\mbox{\it grau\/}(v)=2E=2\times 20 = 40$. O maior
       n\'umero de v\'ertices, consegue-se com todos os v\'ertices de grau
       m\'{\i}nimo, ou seja $\mbox{\it grau\/}(v)=4$ para todo $v\in {\bf V}$. Logo,
       o maior n\'{u}mero poss\'{\i}vel de v\'{e}rtices, $n$, ser\'a aquele tal
       que $4n=40$, o que d\'a $n=10$.

 \item {\footnotesize Prove que sim ou que n\~{a}o:
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item \'{E} poss\'{\i}vel ter um grupo de 9 pessoas, cada uma das quais conhece
              exatamente 5 das outras.
        \item Em qualquer grupo, o n\'{u}mero de pessoas n\~{a}o apertaram as m\~{a}os de um
              n\'{u}mero \'{\i}mpar de pessoas do grupo \'{e} par.
        \item O n\'{u}mero de todos os seres humanos (vivos e mortos) que se casaram
              um n\'{u}mero \'{\i}mpar de vezes \'{e} par.
        \item Em qualquer livraria, o n\'{u}mero de livros com um n\'{u}mero \'{\i}mpar de
              p\'{a}ginas \'{e} par.
       \end{list}}

       {\it Solu\c{c}\~{a}o\/}:

       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Grupo de 9 pessoas, em que cada uma conhece exatamente 5 das
              outras.
              
              Modelando cada pessoa como um v\'ertice e o fato de que uma pessoa
              conhece outra como uma aresta, o problema se reduz \`a
              possibilidade de ter um grafo de 9 v\'ertices de grau 5. Isto \'e
              imposs\'{\i}vel, visto que o n\'umero de v\'ertices de grau
              \'{\i}mpar, em qualquer grafo, \'e par.
              
        \item Em qualquer grupo, o n\'{u}mero de pessoas que n\~{a}o apertaram
              as m\~{a}os de um n\'{u}mero \'{\i}mpar de pessoas do grupo \'{e}
              par.
              
              Modelando cada pessoa como um v\'ertice e o fato de que uma pessoa
              n\~ao apertou as m\~aos de outra como uma aresta, o problema se
              reduz a verificar se em qualquer grafo o n\'umero de v\'ertices de
              grau \'{\i}mpar \'e par. O que \'e verdade.
              
        \item O n\'{u}mero de todos os seres humanos (vivos e mortos) que se
              casaram um n\'{u}mero \'{\i}mpar de vezes \'{e} par.
              
              Modelando cada ser humano como um v\'ertice e o fato de que uma
              pessoa casou com outra como uma aresta, o problema se
              reduz a verificar se em qualquer grafo o n\'umero de v\'ertices de
              grau \'{\i}mpar \'e par. O que \'e verdade.
              
        \item Em qualquer livraria, o n\'{u}mero de livros com um n\'{u}mero
              \'{\i}mpar de p\'{a}ginas \'{e} par.

              Obviamente, o n\'umero de livros com n\'{u}mero \'{\i}mpar de
              p\'{a}ginas pode ser par ou \'{\i}mpar.

       \end{list}

 \item {\footnotesize Prove que se $G$ \'{e} um grafo com exatamente 2 v\'{e}rtices de grau \'{\i}mpar,
       ent\~{a}o ambos os v\'{e}rtices est\~{a}o no mesmo componente.}

       {\it Solu\c{c}\~{a}o\/}:

       Seja um grafo $G$ com exatamente 2 v\'ertices de grau \'{\i}mpar. J\'a
       que o n\'umero de v\'ertices de grau \'{\i}mpar de um grafo \'e par,
       um componente de $G$, que tamb\'em \'e um grafo, n\~ao pode ter apenas
       um dos dois v\'ertices de grau \'{\i}mpar. Logo, ambos devem estar no
       mesmo componente.

 \item {\footnotesize Suponha que um grafo simples $G$ tem $n$ v\'{e}rtices, $n-1$ dos quais de
       grau \'{\i}mpar. Quantos v\'{e}rtices de grau \'{\i}mpar existem em $G^c$?}

       {\it Solu\c{c}\~{a}o\/}:

       O grau de um v\'ertice $v$ em $G^c$ \'e $(n-1)$ menos o grau de $v$ em 
       $G$.Mas, $n-1$ v\'ertices t\^em grau \'{\i}mpar em $G$; logo, $n-1$ \'e
       par, e estes $n-1$ v\'ertices t\^em grau \'{\i}mpar tamb\'em em $G^c$
       (j\'a que um n\'umero par menos um n\'umero \'{\i}mpar s\'o pode
       dar um n\'umero \'{\i}mpar). Evidentemente o outro v\'ertice tem grau
       par tamb\'em em $G^c$.

 \item {\footnotesize Seja $G$ um grafo regular de grau $n$, sendo $n$ \'{\i}mpar. Prove que o
       n\'{u}mero de arestas em $G$ \'{e} divis\'{\i}vel por $n$.}

       {\it Solu\c{c}\~{a}o\/}:

       $\sum_{v\in {\bf V}}\mbox{\it grau\/}(v)=nV$, j\'a que o grafo \'e regular de
       grau $n$. Logo, $nV=2E$; portanto, $V=2E/n$ e, como $n$ \'e
       \'{\i}mpar $E$ tem que ser divis\'{\i}vel por $n$ (para que $V$ seja
       um n\'umero inteiro).

 \item {\footnotesize  Encontre todos os grafos simples de 4 v\'{e}rtices n\~{a}o isomorfos entre si.}


       {\it Solu\c{c}\~{a}o\/}:
       
       Abaixo est\~ao listadas as arestas dos 10 grafos existentes (os
       v\'ertices s\~ao identificados por $a$, $b$, $c$ e $d$):
       \begin{enumerate}
        \item[.] ${\bf E}_1=\{\}$
        \item[.] ${\bf E_2}=\{\{a,b\}\}$
        \item[.] ${\bf E_3}=\{\{a,b\},\{b,c\}\}$
        \item[.] ${\bf E_4}=\{\{a,b\},\{c,d\}\}$
        \item[.] ${\bf E_5}=\{\{a,b\},\{b,c\},\{c,d\}\}$
        \item[.] ${\bf E_6}=\{\{a,b\},\{b,c\},\{b,d\}\}$
        \item[.] ${\bf E_7}=\{\{a,b\},\{b,c\},\{c,d\},\{d,a\}\}$
        \item[.] ${\bf E_8}=\{\{a,b\},\{b,c\},\{c,a\},\{c,d\}\}$
        \item[.] ${\bf E_9}=\{\{a,b\},\{b,c\},\{c,d\},\{d,a\},\{a,c\}\}$
        \item[.] ${\bf E_{10}}=\{\{a,b\},\{b,c\},\{c,d\},\{d,a\},\{a,c\},\{b,d\}\}$
       \end{enumerate}

 \item {\footnotesize Quais pares de grafos da Figura 6-23 (p\'agina 217) do livro texto s\~ao isomorfos?
       Para os que s\~ao d\^e correspond\^encias um-para-um. Para os que n\~ao s\~ao
       mostre porque n\~ao s\~ao.}

 \item {\footnotesize Um grafo simples $G$ tal que $G\cong G^c$ \'{e} dito {\it
       auto-complementar}.
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Encontre um grafo auto-completar com 4 v\'{e}rtices, e outro com
              5.
        \item Prove que o n\'{u}mero de v\'{e}rtices em um grafo
              auto-complementar \'{e} da forma $4k$ ou $4k+1$.
       \end{list}}

       {\it Solu\c{c}\~{a}o\/}:
       
       \begin{list}{(\alph{conta})}{\usecounter{conta}}
        \item Um grafo auto-completar, $G$, com 4 v\'{e}rtices:
              \begin{enumerate}
               \item[.] ${\bf V}_G=\{a,b,c,d\}$
               \item[.] ${\bf E}_G=\{\{a,b\},\{b,c\},\{c,d\}\}$
              \end{enumerate}
              Um grafo auto-completar, $H$, com 5 v\'{e}rtices:
              \begin{enumerate}
               \item[.] ${\bf V}_G=\{a,b,c,d,e\}$
               \item[.] ${\bf E}_G=\{\{a,b\},\{b,c\},\{c,d\},\{d,e\},\{e,a\}\}$
              \end{enumerate}

        \item Ser\'a mostrado que o n\'{u}mero de v\'{e}rtices em um grafo $G$,
              auto-complementar, \'{e} da forma $4k$ ou $4k+1$. Se o grau de um
              v\'ertice $v$ em $G$ \'e {\it grau\/}$(v)$, ent\~ao o grau de
              $v$ em $G^c$ \'e $n-1-\mbox{\it grau\/}(v)$, onde $n$ \'e o
              n\'umero de v\'ertices. Assim, sendo $G$
              auto-complementar, tem-se que \[\sum_{v\in {\bf V}_G}\mbox{\it grau\/}(v)
              =\sum_{v\in {\bf V}_G}(n-1-\mbox{\it grau\/}(v))=n(n-1)-
              \sum_{v\in {\bf V}_G}\mbox{\it grau\/}(v)\mbox{,}\]
              e, portanto, $\sum_{v\in {\bf V}_G}\mbox{\it grau\/}(v)=n(n-1)/2$. Mas,
              como $\sum_{v\in {\bf V}_G}\mbox{\it grau\/}(v)=2E_G$, conclui-se que
              $n(n-1)/2=2E_G$ e, assim, $n(n-1)=4E_G$. Como \'e
              imposs\'{\i}vel ter ambos, $n$ e $n-1$, divis\'{\i}veis por 2,
              ent\~ao, ou $n$ \'e divis\'{\i}vel por 4, ou $n-1$ \'e
              divis\'{\i}vel por 4, ou seja, $n=4k$ ou $n-1=4k$ (neste
              \'ultimo caso, $n=4k+1$).

       \end{list}

 \item {\footnotesize Quais grafos da Figura 6-38 (p\'agina 230) do livro texto s\~ao planares?}

 \item {\footnotesize Suponha que uma imers\~{a}o do grafo simples $G$ no plano tenha 20 faces. Se
       $G$ \'{e} regular de grau 5, quantos v\'{e}rtices cont\'{e}m $G$?}

       {\it Solu\c{c}\~{a}o\/}:
       
       Como $G$ \'e regular de grau 5, tem-se que $5V=2E$. A f\'ormula de
       Euler diz que $V-E+F=2$. Com isto, tem-se que $V-5V/2+20=2$ e,
       portanto, $V=12$.

 \item {\footnotesize Prove que se $G$ \'{e} um grafo planar com $k$ componentes, ent\~{a}o qualquer
       imers\~{a}o de $G$ satisfaz $V-E+F=k+1$.}

       {\it Solu\c{c}\~{a}o\/}:
       
       Sejam $H_1$, $H_2$, \ldots, $H_k$ os $k$ componentes de $G$ ($k\geq 1$).
       Para cada componente $H_i$ tem-se que $V_{H_i}-E_{H_i}+F_{H_i}=2$.
       Portanto, tem-se que:
       \[\sum_{i=1}^{k}(V_{H_i}-E_{H_i}+F_{H_i})=2k\mbox{.}\]
       Mas, $\sum_{i=1}^{k}V_{H_i}=V_G$, $\sum_{i=1}^{k}E_{H_i}=E_G$ e
       $\sum_{i=1}^{k}F_{H_i}=F_G+(k-1)$; esta \'ultima se deve ao fato de que
       a face externa \'e contada uma vez para cada $H_i$. Logo,
       \[V_{G}-E_{G}+F_{G}+(k-1)=2k\mbox{,}\]
       e, portanto, $V_G-E_G+F_G=k+1$

\end{enumerate}

\end{document}
