Sejam G um grafo e M,M ′ dois emparelhamentos de G. Prove que o grafo G′ gerado pela diferença simétrica M△M ′ contém apenas caminhos, vértices...

Sejam G um grafo e M, M' dois emparelhamentos de G. Para provar que o grafo G' gerado pela diferença simétrica M△M' contém apenas caminhos, vértices e ciclos pares, precisamos mostrar que: 1. G' não contém ciclos ímpares 2. G' é conexo Para provar que G' não contém ciclos ímpares, observe que qualquer ciclo em G' deve ser um ciclo em M ou M', mas não em ambos. Isso ocorre porque, se um ciclo estiver em ambos os emparelhamentos, ele será cancelado na diferença simétrica. Além disso, qualquer ciclo em M ou M' deve ter um número par de arestas, pois ambos são emparelhamentos. Portanto, qualquer ciclo em G' deve ter um número par de arestas, o que implica que G' não contém ciclos ímpares. Para provar que G' é conexo, observe que qualquer vértice em G' deve estar em um caminho em M ou M', mas não em ambos. Isso ocorre porque, se um vértice estiver em ambos os emparelhamentos, ele será cancelado na diferença simétrica. Além disso, qualquer caminho em M ou M' deve ter um número par de arestas, pois ambos são emparelhamentos. Portanto, qualquer caminho em G' deve ter um número par de arestas, o que implica que G' é conexo. Portanto, concluímos que o grafo G' gerado pela diferença simétrica M△M' contém apenas caminhos, vértices e ciclos pares.