# Christofides algorithm

I'm trying to implement it from wiki but the step 3 confuses me:

1. Create a minimum spanning tree T of G.
2. Let O be the set of vertices with odd degree in T. By the handshaking lemma, O has an even number of vertices.
3. Find a minimum-weight perfect matching M in the induced subgraph given by the vertices from O.
4. Combine the edges of M and T to form a connected multigraph H in which each vertex has even degree.
5. Form an Eulerian circuit in H.
6. Make the circuit found in previous step into a Hamiltonian circuit by skipping repeated vertices (shortcutting).

Induced subgraph I (from odd vertices of O) is taken over G, so it is complete as well as G so there will be multiple perfect matchings.

All Hungarian/Munkres algorithms which I've seen work with Edmonds matrix. To get Edmonds from an arbitrary complete graph I have to 1) split graph into 2 sets of vertices U, V 2) having a split done, perform a minimum matching search in it.

Choosing different sets U, V will give different minimum perfect matchings weight. So the question is how to get a minimum perfect matching in I having a distance matrix of I.

• The induced subgraph is only using the vertices of O (those with odd degree in T) - there are helpful examples with images on that wiki page... – gilleain Sep 18 '17 at 15:15
• Thanks. I've updated the question. – VladimirLenin Sep 19 '17 at 8:54