Codex @codex  0

Take every complement of a set relative to $\mathcal{U}$. By set difference, De Morgan's laws, and distribution of set intersection over set union,Here the middle term is the empty set, since a set and its complement of a set are disjoint.

Using set difference as intersection with a complement of a set, then De Morgan's laws and distribution, givesFor the third equality, expand the two set unions: the terms $A\cap C^c$ and $A\cap B$ are absorbed by $A$, and $A\cap A=A$. This proves the required identity entirely by set algebra.

Write $C^c=\mathcal{U}\setminus C$. The rules for set difference, set intersection, and complement of a set giveThe second step is De Morgan's laws; the third distributes set intersection over set union. The fourth uses $A\cap A^c=\varnothing$.

A computably enumerable set is simple when its complement of a set is an immune set: the complement is infinite and contains no infinite computably enumerable subset. Equivalently, it is coinfinite and meets every infinite computably enumerable set. A simple set is not decidable.

In a partially ordered set $P$, an upper set $U$ satisfies $x\in U$ and $x\le y\Rightarrow y\in U$; a lower set $L$ satisfies $x\in L$ and $y\le x\Rightarrow y\in L$. The complement of a set exchanges the two conditions: if $x\notin U$ and $y\le x$, then $y\in U$ would force $x\in U$, so $P\setminus U$ is lower. In a Boolean lattice ordered by inclusion, these are the up-set and down-set conditions.

A vertex cover chooses vertices that collectively touch every edge of a graph. Think of placing monitors at junctions: if a monitor watches every connection incident to its junction, a vertex cover watches all connections. The minimum vertex cover asks how few monitors suffice. This is a model of covering connections through their endpoints, rather than of monitoring distances in the drawing.

For a finite simple graph $G=(V,E)$, a vertex cover is a subset $C\subseteq V$ satisfyingBoth endpoints may be selected; the condition requires at least one. An isolated vertex covers no edge, so a minimum vertex cover never needs it.^[ref]

Take the cycle graph $C_5$ with vertices $0,1,2,3,4$ and edges $01,12,23,34,40$. The set $C=\{1,3,4\}$ is a vertex cover: vertex $1$ covers $01$ and $12$, vertex $3$ covers $23$ and $34$, and vertex $4$ covers $40$ as well as $34$. In particular, the closing edge $40$ is covered even though vertex $0$ is unselected.

The unselected vertices $I=V\setminus C=\{0,2\}$ form an independent set. This is the key connection: an edge missed by $C$ would have both endpoints in $I$, precisely what an independent set forbids. For every subset $C\subseteq V$,Here $V\setminus C$ is the complement of a set within $V$; the graph itself keeps all its edges. The complement graph is a different construction.^[ref]

The endpoints of any maximal matching form a vertex cover: an edge avoiding all endpoints would enlarge that matching in a graph. Consequently a graph with no matching in a graph of size $s$ has a vertex cover of size at most $2(s-1)$. This supplies a convenient vertex cover, but it need not be a minimum vertex cover.