So Vertex cover (VC):
Instance: a graph $G$ and an integer $k>0$. Question: Does $G$ have a vertex cover of size at most $k$?
We will now define a version of this problem in which we assume that the degree of each node in a given graph is $2$:
2-vertex cover (2-VC). Instance: a graph $G$ in which each node has degree $2$ and an integer $k>0$. Question: Does $G$ have a vertex cover of size at most $k$?
For the following, decide whether the answer is “Yes”, “No” or “Unknown because it would resolve the $P =? NP$ question.” Prove your claim.
(a) Is $2-VC ≤_P VC$?
(b) Is $VC ≤_P 2-VC$?
and
a second question here
http://pastie.org/private/ljxo6aqg3a9troxpnpxriq
These questions ares really nagging me because i'm not sure what is meant by the phrase degree 2. Is this the cost of the vertex?
Also i'm aware of the general proof of vertex cover that shows how basically we use the compliment of the independent sets to show a vertex cover.
I'm in the middle of revising for exams and these are eluding me, anyone have any suggestions?
UPDATE: I think 1a) is basically just plugging in a 2 degree VC into a graph that can solve the problem in one step and then deriving the answer through that with a cast.