how can we prove that the number of nodes in a minimum node-cover C* of G is greater than the number of edges in a maximum matching M* of G

72 Views Asked by At

Define a node cover $C$ for a graph $G = (V;E)$ to be a set of nodes $C$ such that, for every edge $(u, v)$ that belongs to $E$, $C$ contains at least one of u and v. Define a minimum node-cover of $G$ to be a node-cover that minimizes the number of node in the node cover.

Let $|C*|$ denote the number of nodes in a minimum node-cover $C*$ of $G$, and let $|M*|$ denote the number of edges in a maximum matching $M*$ of $G$. Prove that $|M*| \leq |C*|$.

1

There are 1 best solutions below

4
On

Notice that each edge $(u,v) \in M*$ is incident to a vertex $w_{(u,v)} \in C*$ by the definition of $C*$. Moreover if you consider two different edges $(u_{1},v_{1}), (u_{2},v_{2}) \in M*$, then $w_{(u_{1},v_{1})} \neq w_{(u_{2},v_{2})}$. Otherwise both edges in the matching are incident in $w_{(u_{1},v_{1})} = w_{(u_{2},v_{2})}$, and it is a contradiction with the fact that $M*$ is a matching.

This shows that for each edge in $M*$ one can find a different vertex in $C*$, in other words, we have found an injection from $M*$ to $C*$. It shows that $|M*| \leq |C*|$.