= Solution
The source's explicit parenthetical condition is domination: every unselected <vertex> has a neighbour in the selected <set>. Together with independence this defines an <independent dominating set>. A <first-order sentence> expressing that definition with size at most three is
$$
\boxed{\exists x_1\exists x_2\exists x_3\left(
\bigwedge_{1\leq i<j\leq3}(x_i=x_j\lor\neg E(x_i,x_j))
\ \land\
\forall v\left(\bigvee_{i=1}^3v=x_i\ \lor\ \bigvee_{i=1}^3E(v,x_i)\right)
\right).}
$$
The finite conjunctions and disjunctions abbreviate three explicitly fixed terms, so this is a <first-order formula>. Repeated witnesses allow one- or two-element choices; the first conjunction enforces independence only between distinct selected <vertices>. The last clause says that every <vertex> is selected or adjacent to a selected <vertex>. With the usual nonempty-domain convention, any such choice has size at least one, so repeated witnesses cover all possibilities of size at most three.
For the standard meaning of <independent vertex cover>, replace the domination clause by
$$
\forall u\forall v\left(E(u,v)\to
\left(\bigvee_{i=1}^3u=x_i\ \lor\ \bigvee_{i=1}^3v=x_i\right)\right).
$$
This instead demands that every <edge> has a selected endpoint. These interpretations differ: in a <triangle in a graph>, any singleton is an <independent dominating set>, but no <independent vertex cover> exists. Giving both clauses avoids silently treating the source's two definitions as equivalent.
Back to article page
