In Question 9.3a, it states that if $T=V$, then the minimum cost perfect matching is the minimum cost T-join. Is this actually true? I think I have a counterexample which I have drawn below.
-
2$\begingroup$ The claim is true of the G is a metric space. That is, if you take the shortest path distances induced by the edge lengths and complete the graph then T-join on V is same as min-cost perfect matching. $\endgroup$ – Chandra Chekuri Nov 1 '20 at 15:10
The statement of the problem is incorrect.
But $T$-joins are indeed very much related to the perfect matching problem. What the theorem that 9.3a is supposed to be conveying is:
Assume $G$ is connected.
Suppose that $T = V$. The minimum $T$-join can be found as follows: construct a complete graph $G'$ such that the weight on an edge (a,b) in $G'$ is the length of the shortest path between vertices $a$ and $b$ in $G$. Now, find a minimum weight perfect matching in $G'$. This gives the minimum $T$-join in $G$.
-
$\begingroup$ Thank you, this is exactly what I was looking for. $\endgroup$ – Karagounis Z Nov 1 '20 at 19:54