MO405 - Exercícios - Propostos em 2002-08-19

Nos exercícios que perguntam "verdadeiro ou falso", deve-se justificar a resposta da seguinte forma: se for verdadeiro, com uma prova; se for falso, com um contra-exemplo.

1. (1.3.1 do livro) Verdadeiro ou Falso: Se u e v são os únicos vértices de grau ímpar num grafo G, então G contem um u,v-caminho.
2. (1.3.7 do livro) Determine o número máximo de arestas num subgrafo bipartido de Pn, Cn e Kn.

Soluções - Discutidas em classe em 2002-08-21

1. Temos que mostrar que se G é desconexo então u e v ( únicos vértices de grau ímpar em G) estão no mesmo componente. ( o caso de G conexo é trivial )

   Seja H componente de G tal que u pertence a V(H) e F um outro componente de G ( distinto de H ) tal que v pertence a V(F).

   Em H, exceto pelo vértice u, todos os vértices w tem grau par, portanto:

                        grau(w_1)  +  ... +  grau(w_M) + grau(u)  = X ;  

   onde w_1, w_2, ...... , w_M, u pertencem a V(H).

   X é um número ímpar, contrariando o Teorema Fundamental ( a somatoria dos graus de todos os vértices de um grafo G é igual ao dobro do número de arestas de G ). Logo u deve estar na mesma componente de v para obedecer o teorema fundamental e como H é conexo há um caminho entre u e v.

2. Tipo de Grafo	Número Máximo de Arestas num Subgrafo Bipartido
   Pn	n-1
   Cn	n-1 ( se n é ímpar ) n ( se n é par )
   Kn	Teto(n/2)* Piso(n/2)