Prove Deletion into Bounded Degree Graph is:

a$)$ NP using verifier

b$)$ NP hard, by writing the algorithmic steps using reduction from a known NP hard problem

$-3$sat

$-$vertex cover

$-$clique

Prove Deletion into Bounded Degree Graph is:

a$)$ NP using verifier

b$)$ NP hard, by writing the algorithmic steps using reduction from a known NP hard problem