4. (4.0) Verifique se cada uma das afirmacoes abaixo é falsa ou verdadeira. Se for verdadeira, prove. Se for falsa, dê um contra-exemplo (seu contr...

(a) A afirmação é verdadeira. Para provar isso, podemos usar o Teorema de Euler, que estabelece que em um grafo conexo, a soma dos graus dos vértices é igual ao dobro do número de arestas. No caso de uma floresta com k componentes conexos, cada componente é uma árvore, e uma árvore com n vértices tem n-1 arestas. Portanto, a soma dos graus dos vértices em F é igual a 2m, onde m é o número de arestas. Além disso, cada vértice em uma árvore tem grau pelo menos 1. Portanto, a soma dos graus dos vértices em F é no mínimo k. Portanto, temos a seguinte desigualdade: 2m ≥ k. Como cada vértice em F tem grau no máximo 2, a soma dos graus dos vértices em F é no máximo 2n. Portanto, temos a seguinte desigualdade: 2m ≤ 2n. Combinando as duas desigualdades, temos: k ≤ 2m ≤ 2n. Portanto, m ≥ n - k. (b) A afirmação é verdadeira. Em qualquer grafo, a soma dos graus dos vértices é igual ao dobro do número de arestas. Se o número de vértices com grau ímpar fosse ímpar, a soma dos graus dos vértices seria ímpar, o que é impossível, já que é o dobro do número de arestas. (c) A afirmação é falsa. O grafo bipartido completo Kr,s é hamiltoniano se e somente se r e s forem ambos maiores ou iguais a 2. (d) A afirmação é falsa. Um digrafo pode ter fonte e sumidouro e ainda assim ter ciclos. Por exemplo, considere um digrafo com três vértices A, B e C, onde há uma aresta de A para B, uma aresta de B para C e uma aresta de C para A. (e) A afirmação é falsa. Nem todo grafo que contém um grafo planar como subgrafo é planar. Por exemplo, considere um grafo que consiste em um triângulo e um vértice adicional conectado a todos os vértices do triângulo. O triângulo é um grafo planar, mas o grafo completo não é planar.