I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:

Calculate minimum spanning tree T:

Calculate the set of vertices O with odd degree in T

Same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O

(as all were odd, this should give us the original graph)

Construct a minimum-weight perfect matching M in this subgraph

(I am not sure if I did this right)

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

This is definitely not right.

What went wrong?

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:

Calculate minimum spanning tree T:

Calculate the set of vertices O with odd degree in T. They are the same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O (as all are odd, this should give us the original graph):

Construct a minimum-weight perfect matching M in this subgraph (I am not sure if I did this right) 

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

This is definitely not right. What went wrong?

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:

[![enter image description here][1]][1]

Calculate minimum spanning tree T:

[![enter image description here][2]][2]

Calculate the set of vertices O with odd degree in T

Same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O

(as all were odd, this should give us the original graph) [![enter image description here][1]][1]

Construct a minimum-weight perfect matching M in this subgraph

(I am not sure if I did this right) [![enter image description here][3]][3]

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

[![enter image description here][4]][4]

This is definitely not right.

What went wrong?

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:

Calculate minimum spanning tree T:

Calculate the set of vertices O with odd degree in T

Same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O

(as all were odd, this should give us the original graph)

Construct a minimum-weight perfect matching M in this subgraph

(I am not sure if I did this right)

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

This is definitely not right.

What went wrong?

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:

Calculate minimum spanning tree T:

Calculate the set of vertices O with odd degree in T

Same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O

(as all were odd, this should give us the original graph)

Construct a minimum-weight perfect matching M in this subgraph

(I am not sure if I did this right)

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

This is definitely not right.

What went wrong?

I am following this algorithm example: https://en.wikipedia.org/wiki/Christofides_algorithm#example

The graph:

[![enter image description here][1]][1]

Calculate minimum spanning tree T:

[![enter image description here][2]][2]

Calculate the set of vertices O with odd degree in T

Same as "the minimum spanning tree T" as the degree of all vertices are odd.

Form the subgraph of G using only the vertices of O

(as all were odd, this should give us the original graph) [![enter image description here][1]][1]

Construct a minimum-weight perfect matching M in this subgraph

(I am not sure if I did this right) [![enter image description here][3]][3]

Unite matching and spanning tree T ∪ M to form an Eulerian multigraph

[![enter image description here][4]][4]

This is definitely not right.

What went wrong?