Let G = (V, E) be a simple undirected graph with n = |V | ≥ 1 vertices...

Question

Let G = (V, E) be a simple undirected graph with n = |V | ≥ 1 vertices. A subset U ⊆ V of the vertices is called a vc-set if for every edge {i, j} ∈ E either i ∈ U or j ∈ U (or both). Let $U^∗$ be a vc-set for G that has the smallest size possible (meaning there does not exist any other vc-set $U^{'}$ such that (|$U^{'}$| < |$U^∗$|). A subset W ⊆ V of the vertices of G is called an in-set if for all i, j ∈ W, {i, j} $\notin$ E. Let $W^∗$ be a largest possible in-set in G (meaning there is no other in-set, $W^{'}$, such that |$W^∗$| < |$W^{'}$|). Prove that |$W^*$| = n − |$U^∗$ |. I tried to use the basics of graph theory but was of no use as I got stuck and back to the starting point. If you could help me I would be really grateful thanks a ton!

Answer 1

You can show, that for every x,y which belong to V\U* holds that {x,y} is not an edge. Otherwise x or y is in U* (contradiction). So |W*| is greater than or equal to |V\U*|. Also there exists no other W' with more vertices than V\U*. Because V\W' would be vertex cover smaller than U (contradiction).

There for n = |U*| + |V\U*| = |U*| + |W*|.

Sorry for my broken english.

Answer 2

We use the fact: the complement of vc-set is an in-set and vice versa.

V\W* is vc-set then |V\W*| $\geq$ |U*| which means |V\W*| $=$ n - |W*| $\geq$ |U*|.

V\U* is in-set then |V\U*| $\leq$ |W*| which means |V\U*| $=$ n - |U*| $\leq$ |W*|.

Putting both inequalities together yields n $=$ |U*| + |W*|