patternMinor
Is a perfect matching's weight less than MST of a metric graph?
Viewed 0 times
graphthanperfectweightmetriclessmstmatching
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#91597, answer score: 2
Revisions (0)
No revisions yet.