Casamento mínimo em grafo

[rs.fran]

Boa noite!

Estou implementando o algoritmo de Christofides, e um dos passos para implementação é obter o casamento mínimo entre os vértices de grau ímpar para torná-los de grau par. Eu entendi que o casamento mínimo é colocar arestas entre os vértices de grau ímpar de modo que todos passem a ter grau par. Porém, essas arestas tem que ser colocada de uma maneira que a soma dos pesos seja mínima. Pensei em combinar todas as maneiras possíveis de casamento e então pegar a menor, porém, com muitos vértices, isso seria inviável... Vocês podem me ajudar a pensar em alguma estratégia? Obrigada