Minimum Vertex Cover

Last updated Nov 1, 2022

Let $G$ be an Undirected Graph and let $\mathcal{C} = {C \subset V(G) : C \text{ is a Vertex Cover}}$. Then a Minimum Vertex Cover is a Vertex Cover $C \in \mathcal{C}$ so that $|C| = \min {|C| \leq |V(G)| : C \in \mathcal{C}}$.

1. Note this definition is Well-Defined even for Infinite Sets because Cardinals form a Well-Ordering.
2. The Set Cardinality of a Minimum Vertex Cover on $G$ is denoted $\tau(G)$.