1. Grafo e Subgrafo; Arvores e Conectividade 1.1 . Prove que para toda árvore com n vértice, o número de arestas m = n −1. 1.2 . Mostre que há onze...

1.1. Para provar que toda árvore com n vértices possui n-1 arestas, podemos utilizar o princípio da indução matemática. Base: Para n=1, temos uma árvore com apenas um vértice e nenhuma aresta, portanto a afirmação é verdadeira. Hipótese: Suponha que a afirmação seja verdadeira para uma árvore com k vértices, ou seja, que essa árvore possui k-1 arestas. Passo da indução: Vamos considerar uma árvore T com k+1 vértices. Escolhemos um vértice folha (um vértice que possui apenas uma aresta conectada a ele) e removemos esse vértice e sua aresta. Isso resulta em uma árvore T' com k vértices, que pela hipótese de indução possui k-1 arestas. Agora, adicionamos o vértice folha novamente, conectando-o a um vértice qualquer de T'. Como resultado, T possui k+1 vértices e k arestas. Portanto, a afirmação é verdadeira para toda árvore com n vértices. 1.2. Existem onze grafos simples não-isomorfos com quatro vértices. Uma maneira de encontrá-los é desenhar todos os grafos possíveis com quatro vértices e verificar quais são isomorfos. Outra maneira é utilizar a fórmula de Polya, que é um método mais geral para contar objetos não-isomorfos. 1.3. O grafo completo Kn possui n(n-1)/2 arestas. 1.4. • Para o grafo bipartido completo Kn1,n2, cada vértice de uma partição está conectado a todos os vértices da outra partição, portanto o número de arestas é n1*n2. • Para um grafo simples e bipartido G, podemos dividir os vértices em duas partições A e B. Cada vértice em A pode estar conectado a no máximo n2 vértices em B, e vice-versa. Portanto, o número máximo de arestas é n1*n2. Como G é um grafo simples, cada aresta é contada duas vezes, então o número de arestas é no máximo n1*n2/2. Como n1+n2=n, temos que n1=n/2 e n2=n/2, portanto |E(G)| ≤ n2/4. 1.5. A soma dos graus de todos os vértices é igual ao dobro do número de arestas, ou seja, ∑v∈V d(v) = 2|E|. 1.6. Seja G um grafo com n vértices. Podemos dividir os vértices em dois conjuntos: A, contendo os vértices com grau par, e B, contendo os vértices com grau ímpar. Como a soma dos graus de todos os vértices é par (pela questão 1.5), o número de vértices em A é par. Portanto, o número de vértices em B (com grau ímpar) também é par. 1.7. Se um grafo é bipartido, podemos dividir seus vértices em dois conjuntos A e B, de forma que todas as arestas conectem um vértice de A a um vértice de B. Se um ciclo ímpar existisse, ele teria que alternar entre vértices de A e B, o que é impossível. Por outro lado, se um grafo não possui ciclo ímpar, podemos colorir seus vértices com duas cores, de forma que vértices adjacentes tenham cores diferentes. Essa coloração define uma bipartição do grafo. 1.8. Se existe um (u, v)-passeio em G, podemos escolher um passeio P que passe pelo menor número possível de vértices. Se P não contém vértices repetidos, então ele é um (u, v)-caminho simples e estamos prontos. Caso contrário, P contém um ciclo C. Podemos remover todas as arestas de C de G, obtendo um grafo G' que ainda contém um (u, v)-passeio. Como P passa pelo menor número possível de vértices, o passeio em G' passa por menos vértices do que P. Portanto, podemos repetir esse processo até obter um (u, v)-caminho simples. 1.9. Se G é uma árvore, ela é conexa e não possui ciclos. Portanto, se removermos uma aresta qualquer de G, o grafo resultante será desconexo. Isso significa que toda aresta de G é uma ponte. Por outro lado, se G é um grafo conexo e toda aresta é uma ponte, então ele não possui ciclos. Se removermos uma aresta qualquer de G, o grafo resultante será desconexo. Portanto, G é uma árvore. 1.10. Um exemplo de grafo com 5 vértices em que a clique máxima e o conjunto independente máximo são menores que 3 é o grafo formado por um pentágono e um vértice central conectado a todos os vértices do pentágono. A clique máxima e o conjunto independente máximo desse grafo possuem apenas dois vértices cada.