How can we prove that, for a connected graph, the maximum independent set is not larger than the minimum edge cover? Thanks.
[Math] Maximum independent set $\leq$ Minimum edge cover
graph theory
graph theory
How can we prove that, for a connected graph, the maximum independent set is not larger than the minimum edge cover? Thanks.
Best Answer
If graph $G$ is connected, every vertex has at least one edge, unless it consists of a single vertex (an exceptional case where there is no edge cover).
Suppose $S$ is an independent set and $E$ is an edge cover. Then for each vertex $v\in S$ there exists at least one edge $e\in E$ incident with $v$.
By definition of independent set no two $u,v \in S$ have a common edge in $E$.
Therefore $|S| \le |E|$.