# What's the vertex cover of the null graph?

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.

• You can always remove vertices of degree at most two trivially in vertex cover. Isolated vertices can be removed, the neighbor of a leaf can be removed by decreasing the budget by one. Degree two vertices are left to the reader. – Pål GD May 8 '13 at 17:55
• I didn't understand you ! the reduction from 3-SAT to Vertex Cover is described in Sipser book , there he mention that there are in the graph a vertex cover of size $k=n+2m$ while total number of vertices is $2n+3m$ so we have : $l=\frac{k}{2n+3m}$ so I want to increase the number of vertices such that : $l=\frac{n+2m}{2n+4m}=\frac12$ – Fayez Abdlrazaq Deab May 8 '13 at 20:08