[Solved]: What's the vertex cover of the null graph?

Problem Detail: 

Let $N(G)$ be the null graph. What's the number of vertex cover for this graph? I wanted to modify the reduction from SAT to vertex cover by adding vertices that are not connect to any vertices.

Asked By : Fayez Abdlrazaq Deab

Answered By : Luke Mathieson

The minimum vertex cover for a totally disconnected graph is the empty set. A vertex cover is a set of vertices that covers all the edges, i.e. every edge in the graph needs at least one of its endpoints in the vertex cover, so if there are no edges in the graph, no edges need covering.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/11865