Abhijeet Mulgund's Personal Webpage

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

If $E(G)$ is a Finite Set

...

11/7/2022

, then the definition holds If and Only If

If and Only If

...

11/7/2022

$|{e \in E(G) : e \cap C \neq \emptyset}| = |E(G)|$ .

Backlinks

Konig's Theorem

Konig's Theorem

Statement Suppose $G = (V, E)$ is a . Then the is strict. That is, $\tau(G) = \nu(G)$ . Proof - See , early on, but I forget what page Sources Original source? Other Outlinks ...

11/7/2022
Minimum Vertex Cover

Minimum Vertex Cover

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

11/7/2022
Vertex Cover

Vertex Cover

... $C \subset V(G)$ is a s.t. $\{e \in E(G) : e \cap C \neq \emptyset\} = E(G)$ . Remarks If $E(G)$ is a , then the definition holds $|\{e \in E(G) : e \cap C \neq \emptyset\}| =......

11/7/2022

Interactive Graph