TAOCP 7.1.4 Exercise 13
Let $G=(V,E)$ be an ordinary (undirected) graph, viewed as a digraph by replacing each edge ${u,v}\in E$ with the two arcs $u\to v$ and $v\to u$.
Section 7.1.4: Binary Decision Diagrams
Exercise 13. [M15] [M15] How is the concept of a graph kernel related to the concept of (a) a maximal clique? (b) a minimal vertex cover?
Verified: no
Solve time: 3m34s
Solution
Let $G=(V,E)$ be an ordinary (undirected) graph, viewed as a digraph by replacing each edge ${u,v}\in E$ with the two arcs $u\to v$ and $v\to u$. From Exercise 12(a), a kernel of this symmetric digraph is exactly a maximal independent set $K\subseteq V$, meaning no two vertices in $K$ are adjacent and $K$ is inclusion-maximal with this property.
(a) Relation to maximal cliques
Let $\overline{G}$ denote the complement graph of $G$, with the same vertex set $V$ and edges ${u,v}$ whenever ${u,v}\notin E$. A set $C\subseteq V$ is a clique in $G$ if and only if it is an independent set in $\overline{G}$, since every pair of vertices in $C$ is adjacent in $G$ exactly when no pair is adjacent in $\overline{G}$.
Maximality is preserved under this correspondence. If $C$ is a maximal clique in $G$, then it is not contained in any larger clique, hence it is not contained in any larger independent set of $\overline{G}$, so it is a maximal independent set in $\overline{G}$. Conversely, any maximal independent set in $\overline{G}$ is a maximal clique in $G$.
From Exercise 12(a), maximal independent sets in an undirected graph are exactly kernels of the corresponding symmetric digraph. Applying this to $\overline{G}$ shows that maximal cliques in $G$ correspond exactly to kernels in the symmetric digraph of $\overline{G}$.
(b) Relation to minimal vertex covers
A vertex cover in $G$ is a set $S\subseteq V$ such that every edge of $G$ has at least one endpoint in $S$. Its complement $V\setminus S$ contains no edge of $G$, hence is an independent set. Conversely, if $I$ is an independent set, then $V\setminus I$ is a vertex cover, since any uncovered edge would have both endpoints in $I$.
Thus complements of vertex covers are precisely independent sets, and complements of minimal vertex covers are precisely maximal independent sets: if $S$ is a minimal vertex cover, then $V\setminus S$ is an independent set that cannot be enlarged without losing independence, hence it is a maximal independent set. Conversely, complements of maximal independent sets are minimal vertex covers.
From Exercise 12(a), maximal independent sets are kernels in the symmetric digraph of $G$. Therefore minimal vertex covers are complements of kernels in that digraph.
This completes the proof. ∎