Greedy Matching in weighted graphs

Question

Suppose there is an edge weighted graph. We will find a matching M by greedily adding the maximum weighted edge and keep on going until no more edges can be added. I need to prove that the weight of this matching is at least half of maximum matching.

Progress so far: I have been trying to solve this problem by taking the symmetric difference between the Maximum matching and the greedy matching. A couple of observations I have are:

1. There cannot be any component in the symmetric difference of length 1 since it can be added to either of the matching's and increase their size.
2. If there is a component of length 2 then both of them will be of equal weight because otherwise the heavy edge will have to go to greedy matching and the lighter to maximum. This is not possible since if that is the case we can always take the heavier edge for the maximum matching as well
3. For a component of length 3 - there will always be two edges from maximum matching and one from greedy matching because otherwise the weight of greedy matching in that component will always be greater than the maximum matching and thus we could change the maximum matching to get a matching of more weight. Now, let the weight of greedy matching edge be G1 and weight of maximum matching be M1 & M2. G1>= M1 && G1>=M2 but M1+M2 >= G1, from this we can see that G1>=(M1+M2)/2
4. For a general component of n length - This is the part where I am stuck and not able to make progress. While I am able to make some observations for components of length more than 3 but haven't been able to generalize till now.

I am aware that there are other methods but I am interested in solving it using this method. I feel that I am very close and there is some certain theorem from other mathematical domains that can be used to solve this but not sure though.

Answer 1

Edit: I haven't seen the word "weighted". Below is a solution for the unweighted version. I will leave it nevertheless, as it provides some key ideas for the weighted case. You are actually essentially done! But I will still write everything down once more for the sake of completeness. I will also add more details for future readers.

We consider the symmetric difference $\Delta=(M\setminus M')\cup (M'\setminus M)$, where I denote the maximum matching with $M$ and the greedy matching with $M'$. As you have implicitly used, no vertex of $(V,\Delta)$ has degree $\geq3$ because this would imply the existence of two incident edges in $M$ or $M'$, both of which are matchings. Therefore, this graph consists of:

1. paths of length $\geq0$
2. cycles

Now, in these subgraphs, the "belongings" of the edges must alternate, so that no two incident edges are both from $M$ or both from $M'$. This immediately implies that the cycles must be of even length. Note that $$|M\setminus M'|\leq2|M'\setminus M| \Rightarrow |M|=|M\setminus M'|+|M\cap M'|\leq2|M'\setminus M|+2|M\cap M'|=2|M'| $$ so it suffices to show the first inequality.

As you have noted, there cannot be any path of length 1, because either some incident edge of this path-edge (in the original graph) is in the intersection of $M$ and $M'$ (this means that it cannot belong to either, contradiction) or all incident edges of this edge are outside of $M$ or $M'$ (so it can be added to either, contradiction to how we defined $M$ and $M'$). We therefore look only at the paths of length $\geq2$ and even-length cycles. Note that, if we reduce the inequality to each connected component and then add up all these inequalities, we get the desired inequality. Therefore, without loss of generality, we have only one component.

This component $C$ has alternating edges from $M$ and $M'$, so either $|M\cap C|=|M'\cap C|$ (number of edges is even) or $|M\cap C|=|M'\cap C|+1$ (number of edges is odd). For the latter, we use a generalization of your third point. Namely, if it was the other way around (these are the only two possibilities because of alternating), we could "flip" the sides to get $M$ bigger, but it was maximum! Note that here one should pay a little attention as to why it would be allowed to flip sides (analogous to the case of 1-paths).

In either case, $$|M\setminus M'|\leq|M'\setminus M|+1\leq 2|M'\setminus M|$$ and we are done.

---

Now the weighted case. Most of the argument actually carries over, namely the cases are the same. Again wlog one component. First off, consider the heaviest edge $e_1$ of the component $C$ (potentially tiebreaking over order of greedy algorithm). This is certainly in $M'\setminus M$, because by the time it was considered, it was feasible (as every other potential 'obstacle' in $C$ is at most as heavy). Same goes for the second $e_2$ - almost, because it is either in $M'\setminus M$ or it is incident to $e_1$. Iterating this, every edge in $e_i$ is either in $M'\setminus M$ (=feasible when it was considered) or it is incident to some edge in $M'\setminus M$ that has more weight than it (so it was already in $M'\setminus M$ when considered, whence $e_i$ was "declined"). In other words, every edge in $M\setminus M'$ has a neighbor with more weight than it. Since every $e\in M'\setminus M$ has at most two neighbors, we count hereby every neighbor at most twice, therefore $c(M\setminus M')\leq 2c(M'\setminus M)$.