6 System of distinct representatives 6.2 Latin rectangles and decomposition of doubly stochastic matrices 6.4 Gallai’s and Berge’s theorems

6.3 Independent Sets and Covers: Konig, Egervary theorem

Definition 6.13 (Independent sets and covers).

An independent set of vertices is $S\subset V$ such that no two vertices in $S$ are adjacent. A subset of vertices $S\subset V$ is a vertex cover if every edge in $G$ is incident to at least one vertex in $S$ . An edge cover is a set of edges $E^{\prime}\subset E$ such that every vertex is contained in at least one edge in $E^{\prime}$ .

For the relevance of independent sets to information theory/communication, see Section 6.8.

Definition 6.14 (Independence number and cover number).

$\displaystyle\alpha(G)$	$\displaystyle=$	$\displaystyle\max\{\|S\|:S\,\mbox{independent vertex set}\}.$
$\displaystyle\alpha^{\prime}(G)$	$\displaystyle=$	$\displaystyle\max\{\|M\|:M\,\mbox{independent edge set}\}.$
$\displaystyle\beta(G)$	$\displaystyle=$	$\displaystyle\min\{\|S\|:S\,\mbox{vertex cover}\}.$
$\displaystyle\beta^{\prime}(G)$	$\displaystyle=$	$\displaystyle\min\{\|E^{\prime}\|:E^{\prime}\,\mbox{edge cover}\}.$

A matching $M$ is said to be maximal if there is no matching $M^{\prime}$ such that $M\subsetneq M^{\prime}$ . A matching $M$ is said to be a maximum matching if $\alpha^{\prime}(G)=|M|$ . Similarly we define maximal/maximum independent set and minimal/minimum vertex/edge cover.

Exercise(A) 6.15.

Prove that a graph G is bipartite if and only if every subgraph H of G has an independent set consisting of at least half of V(H).

We first derive some trivial relations between the four quantities. If $M$ is a maximum matching, then to cover each edge we need distinct vertices and hence the vertex cover should have size at least $|M|$ . Furthermore, given a maximum matching $M$ , $V(M)$ gives a vertex cover. For if there is an edge $e$ not covered by $V(M)$ then $M+e$ is a larger matching than $M$ . These observations yield the first inequality below.

\alpha^{\prime}(G)\leq\beta(G)\leq 2\alpha^{\prime}(G)\,\,\,;\,\,\,\alpha(G)% \leq\beta^{\prime}(G).

As for the second inequality, observe that to cover vertices of an independent set, we need distinct edges.

Lemma 6.16.

Let $G$ be a graph. $S\subset V$ is an independent set iff $S^{c}$ is a vertex cover. As a corollary, we get $\alpha(G)+\beta(G)=n=|V|.$

The above lemma follows trivially from the definitions.

Theorem 6.17 (Konig, Egervary, 1931).

For a bi-partite graph, $\alpha^{\prime}(G)=\beta(G)$ .

Remark 6.18 (Equivalent Formulation :).

A bi-partite graph is equivalent to a $0-1$ matrix. Denote the rows by $V_{1}$ and columns by $V_{2}$ . If $(v_{1},v_{2})$ -entry is a $1$ then there is an edge $v_{1}\sim v_{2}$ . It is easy to see that given a bi-partite matrix it can be represented as a $0-1$ matrix with rows indexed by $V_{1}$ and columns indexed by $V_{2}$ .

By a line, we shall mean either a row or a column. Under the matrix formulation, vertex cover is a set of lines that include all the $1$ ’s. An independent set of edges is a collections of $1$ ’s such that no two $1$ ’s are on the same line.

Proof.

We will show that for a minimum vertex cover $Q$ , there exists a matching of size at least $|Q|$ . Partition $Q$ into $A:=Q\cap V_{1}$ and $B:=Q\cap V_{2}$ . Let $H$ and $H^{\prime}$ be induced subgraphs on $A\sqcup(V_{2}-B)$ and $(V_{1}-A)\sqcup B$ respectively. If we show that there is a complete matching on $A$ in $H$ and a complete matching on $B$ in $H^{\prime}$ , we have a matching of size at least $|A|+|B|$ ( $=|Q|$ ) in $G$ . Also, note that it suffices to show that there is a complete matching on $A$ in $H$ because we can reverse the roles of $A$ and $B$ apply the same argument to $B$ as well.

Since $A\cup B$ is a vertex cover, there cannot be an edge between $V_{1}-A$ and $V_{2}-B$ . Suppose for some $S\subset A$ , we have that $|N_{H}(S)|<|S|$ . Since $N_{H}(S)$ covers all edges from $S$ that are not incident on $B$ , $Q^{\prime}:=Q-S+N_{H}(S)$ is also a vertex cover. By choice of $S$ , $Q^{\prime}$ is a smaller vertex cover than $Q$ contradicting that $Q$ is minimum. Hence, we have that Hall’s condition holds true for $A$ in $H$ . And by the arguments in the previous paragraph, the proof is complete. ∎