This is part of a bigger proof I'm trying to solve, which eventually came down to one thing:

Let $G=(V,E)$ an un-directed, complete, metric graph (maintains the triangle inequality) with an even number of vertices. Let $PM$ denote a minimum-weight-perfect matching on $E$ and let $MST$ denote a minimum-spanning-tree of $G$.

Is it true that $w(PM) \leq w(MST)$ ?

I'm not sure if the fact that the graph is metric is useful, but I have pointed that out any way.

I know $PM$ and $MST$ do not necessarily share all edges, but maybe some of them? I was trying and couldn't find a counter-example to disprove this.

My gut says it's true, but I cannot find a definitive way to prove it.

  • 1
    $\begingroup$ Is $G$ a complete graph? If so, I can see a way to prove this: Transform the MST into a PM by repeatedly finding either a cherry (a path $uvx$ such that $u$ and $x$ are leaves) or a pendant 2-path (a path $uwx$ such that $u$ is a leaf and $x$ has degree 2), and transforming it into a new, single-edge component $ux$. If there are an even number of vertices then this can always be done, with each step not increasing the total graph weight (in the cherry case we need the triangle inequality to show $w(uw) \le w(uv) + w(vx)$) eventually producing a PM, and the MWPM is no worse. $\endgroup$ – j_random_hacker May 7 '18 at 20:36
  • $\begingroup$ Perhaps you could update to answer my question, "Is $G$ a complete graph?" $\endgroup$ – j_random_hacker May 8 '18 at 8:49
  • $\begingroup$ @j_random_hacker Yes $G$ is complete $\endgroup$ – shaqed May 8 '18 at 8:59

Given any spanning tree, here is how to construct a perfect matching with weight no larger. We consider two cases.

Case 1. The tree has some leaf $\ell$ which is an only child of its "parent" $x$. In this case we add $(\ell,x)$ to the matching, delete the vertices $\ell,x$, and continue.

Case 2. The tree has some leaf $\ell_1$ which has a sibling $\ell_2$. Let the common "parent" be $x$. The triangle inequality shows that $w(\ell_1,\ell_2) \leq w(\ell_1,x) + w(\ell_2,x)$. Accordingly, we add $(\ell_1,\ell_2)$ to the matching, delete the vertices $\ell_1,\ell_2$, and continue.

At each point in time, the remaining graph is always a tree, and the removed vertices are covered by a matching. Furthermore, the cost of the matching is always at most the cost of the edges removed from the tree. Eventually all the vertices will be exhausted, and we will be left with a perfect matching whose cost is at most the cost of the tree.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.