1. (1,5 pts) Use o Teorema de König–Egerváry para provar que todo grafo bipartido G tem um emparalhamento de tamanho pelo menos e(G)/∆(G). 2. (0,...

1. Para provar que todo grafo bipartido G tem um emparelhamento de tamanho pelo menos e(G)/∆(G), podemos usar o Teorema de König-Egerváry. Este teorema afirma que, em um grafo bipartido G, o tamanho máximo de um emparelhamento é igual ao tamanho mínimo de uma cobertura por vértices. Seja M um emparelhamento máximo em G e C um conjunto mínimo de vértices que cobre todas as arestas de G. Como G é bipartido, podemos dividir C em dois conjuntos X e Y, onde X é o conjunto de vértices em uma partição de G e Y é o conjunto de vértices na outra partição. Como C é uma cobertura por vértices, cada aresta de G tem pelo menos uma extremidade em C. Como M é um emparelhamento máximo, cada vértice em X (ou Y) pode ser a extremidade de no máximo uma aresta em M. Portanto, temos que: | M | ≤ | C | / 2 ≤ (| X | + | Y |) / 2 = n / 2 onde n é o número total de vértices em G. Além disso, como G é bipartido, temos que ∆(G) = n / 2. Portanto, temos que: | M | ≤ n / (∆(G)) = e(G) / ∆(G) 2. Usando o resultado acima, podemos concluir que todo subgrafo de Kn,n com mais de n(k-1) arestas tem um emparelhamento de tamanho pelo menos k. Para ver isso, observe que um subgrafo de Kn,n é bipartido e tem n vértices em cada partição. Portanto, temos que ∆(G) = n e e(G) ≥ n(k-1)+1. Substituindo esses valores na desigualdade acima, obtemos: | M | ≤ e(G) / ∆(G) ≥ (n(k-1)+1) / n = k - 1/n + 1/nk Como k é um número inteiro, temos que | M | ≥ k. Portanto, todo subgrafo de Kn,n com mais de n(k-1) arestas tem um emparelhamento de tamanho pelo menos k.