TIFR CSE 2016 | Part B | Question: 10

Question

A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $I \subseteq V(G)$ such that no edge has both its endpoints in $I$. Which of the following is TRUE of every graph $G$ and every vertex cover $C$ of $G$?

• A. There exists an independent set of size $\mid C \mid$
• B. $V(G) -C$ is an independent set
• C. $\mid C \mid \: \: \geq \: \: \mid E(G)\mid /2$
• D. $\mid C \mid \: \:  \geq \: \: \mid V(G)\mid /2$
• E. $C$ intersects every independent set

Answer 1

option A: False
There exists an independent set of size ∣C∣

This may not be true always as the independent set can be empty .ie, all the vertices may be included in the vertex cover( even both the end points of every edge as it is not a minimum vertex cover).

option B True

For any graph V(G)−C is an independent set

Reason: there will be no edge between the vertices of I set as per the definition of vertex cover. There is no edge with both sides belonging to independent set(if so then the subset is not vertex cover)

option C & D can be proved wrong using a complete graph with a vertex in the centre.

option E : False

Consider a graph with an isolated vertices. It falls in independent set. So intersection is empty.

Comments

@Manoja Rajalakshmi A Could you please explain how option (A) is right.

In Question, it is mentioned term "Vertex cover" but not "Minimum Vertex Cover" as vertex cover can have all the vertices of the graph (in worst case) but there is no any independent set which contains all the vertices in graph (except the case when each vertex is isolated vertex). So in my view option (A) is also wrong Only option (B) is right.

Correct me if i am wrong.

---

Yes you are right. I have edited the answer.

There is a possibility of an independent set of size |C|, but it is not true for every graph( as mentioned in question).