Abhijeet Mulgund's Personal Webpage

Search

Search IconIcon to open search

Vertex Cover

Last updated Nov 1, 2022

# Definition

Let $G$ be an Undirected Graph. A Vertex Cover $C \subset V(G)$ is a Set s.t. ${e \in E(G) : e \cap C \neq \emptyset} = E(G)$.

# Remarks

  1. If $E(G)$ is a Finite Set, then the definition holds If and Only If $|{e \in E(G) : e \cap C \neq \emptyset}| = |E(G)|$.