= Solution
\b[The nonempty <simple graphs> having an <independent vertex cover> of size at most two.] The witnesses $x,y$ select the cover. The clause $\neg E(x,y)$ makes the selected <vertices> nonadjacent; the universal clause forbids every <edge> whose two endpoints both lie outside the selected <set>.
The witnesses need not be distinct, so a one-<vertex> cover is permitted by choosing $x=y$. A nonempty edgeless <graph> also satisfies the formula. The empty <graph> does not, because the existential <quantifiers> have no witnesses. Here <independent vertex cover> has its standard <vertex cover> meaning; 8(b)'s differing parenthetical definition is addressed separately below.
Back to article page
