# Reducing the min weight perfect matching problem to a T-join

My lecture notes for $$T$$-joins states:

If $$T = V$$ then $$T$$ -joins of cardinality $$V/2$$ are exactly the perfect matchings of $$G$$ = $$(V ,E)$$. So, the minimum weight perfect matching problem can be reduced to the minimum weight $$T$$ -join problem by adding a large constant to each edge weight (to get a degree of 1 for each vertex in a $$T$$-join.)

I agree with this but I don't see how adding a large constant to each edge weight restricts the degree of each vertex to 1 in the $$T$$-join.

Since the algorithm is adding a large positive weight to each edge, the minimum weight $$T$$-join will have the minimum number of edges in it. Note that the least number of edges in a $$T$$-join for $$T = V$$ could be $$|V|/2$$. That is, each vertex has degree exactly $$1$$.
• How does adding a large constant gaurantee that the $T$-join has the minimum number of edges in it? May 22, 2023 at 20:05
• @SVMteamsTool Suppose you add constant $c \gg |E| \cdot max_{e \in E} \{ w_e \}$, then any $T$-join with $k+1$ edges will have larger weight than any $T$-join with $k$ edges. Can you prove this statement? May 22, 2023 at 20:09