<p>The statement of the problem is incorrect.</p>
<p>But <span class="math-container">$T$</span>-joins are indeed very much related to the perfect matching problem. What the theorem that 9.3a is supposed to be conveying is:</p>
<p>Assume <span class="math-container">$G$</span> is connected.</p>
<p>Suppose that <span class="math-container">$T = V$</span>. The minimum <span class="math-container">$T$</span>-join can be found as follows: construct a complete graph <span class="math-container">$G'$</span> such that the weight on an edge (a,b) in <span class="math-container">$G'$</span> is the length of the shortest path between vertices <span class="math-container">$a$</span> and <span class="math-container">$b$</span> in <span class="math-container">$G$</span>. Now, find a minimum weight perfect matching in <span class="math-container">$G'$</span>. This gives the minimum <span class="math-container">$T$</span>-join in <span class="math-container">$G$</span>.</p>

CC BY-SA 4.0
2020-11-01T19:54:00.663Z
Thank you, this is exactly what I was looking for.
Karagounis Z
CC BY-SA 4.0
2020-11-01T11:17:02.177Z
2020-11-01T11:17:02.177Z
Peter Shor 
<p><a href="https://i.sstatic.net/xeUK6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/xeUK6.png" alt="enter image description here" /></a></p>
<p>In Question 9.3a, it states that if <span class="math-container">$T=V$</span>, 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 <a href="https://i.sstatic.net/bNGJ1.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/bNGJ1.png" alt="enter image description here" /></a>below.</p>

CC BY-SA 4.0
2020-11-01T15:10:23.203Z
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.
Chandra Chekuri
<graph-theory><co.combinatorics><approximation-algorithms><optimization><linear-programming>
Is this homework problem on T-joins wrong?
Karagounis Z
# Is this homework problem on T-joins wrong?

(Asked by: username_0 on 2020-11-01)

[![enter image description here](https://i.sstatic.net/xeUK6.png)](https://i.sstatic.net/xeUK6.png)

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 [![enter image description here](https://i.sstatic.net/bNGJ1.png)](https://i.sstatic.net/bNGJ1.png)below.

**Tags:** graph-theory, co.combinatorics, approximation-algorithms, optimization, linear-programming
> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2020-11-01. Score: 2 | Accepted answer

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$.

> **Comments:**
> **username_0**: Thank you, this is exactly what I was looking for.  

---

