Let $G = (V, E)$ be a simple undirected graph with $n = |V | \ge 1$ vertices.

Question

Let $G = (V, E)$ be a simple undirected graph with $n = |V | \ge 1$ vertices. A subset $U \subseteq V$ of the vertices is called a vc-set if for every edge $\{i, j\} \in E$ either $i \in U$ or $j \in U$ (or both). Let $U^∗$ be a vc-set for $G$ that has the smallest size possible (meaning there does not exist any other vc-set $U'$ such that ($|U'| < |U^∗|$). A subset $W \subseteq V$ of the vertices of $G$ is called an in-set if for all $i, j \in W, \{i, j\} \not\in E$. Let $W^∗$ be a largest possible in-set in $G$ (meaning there is no other in-set, $W′$, such that $|W^∗| < |W^{'}|$). Prove that $|W^∗| = n − |U^∗|$. I tried to use the basics of graph theory but was of no use as I got stuck and back to the starting point. If you could help me I would be really grateful thanks a ton!

Answer 1

It suffices to show that for any vc-set $U$, its complement is an in-set.