The following problem is from my algorithms class:

Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\ge 2 $ and $\delta(G(V_2))\ge 3 $, where $G(V_1)$ denotes the subgraph induced by $V_1$ and $\delta(G(V_1))$ denotes the minimum degree of graph $G(V_1)$. Prove this decision problem is NP complete.

I'm trying to prove $$PARTITION \le_p This-Problem$$ but haven't came up with a solution until now. I've never met a problem dealing with the minimum depth of a graph. Is there any theorem about it? Could anyone help me out here?

The following problem is from my algorithms class:

Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\ge 2 $ and $\delta(G(V_2))\ge 3 $, where $G(V_1)$ denotes the subgraph induced by $V_1$ and $\delta(G(V_1))$ denotes the minimum degree of graph $G(V_1)$. Prove this decision problem is NP complete.

I'm trying to prove $$\text{PARTITION} \le_p \text{This-Problem}$$ but haven't came up with a solution until now. I've never met a problem dealing with the minimum depth of a graph. Is there any theorem about it? Could anyone help me out here?

The following problem is from my algorithms class:

Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\le 2 $ and $\delta(G(V_2))\le 3 $, where $G(V_1)$ denotes the subgraph induced by $V_1$ and $\delta(G(V_1))$ denotes the minimum degree of graph $G(V_1)$. Prove this decision problem is NP complete.

I'm trying to prove $$PARTITION \le_p This-Problem$$ but haven't came up with a solution until now. I've never met a problem dealing with the minimum depth of a graph. Is there any theorem about it? Could anyone help me out here?

The following problem is from my algorithms class:

Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\ge 2 $ and $\delta(G(V_2))\ge 3 $, where $G(V_1)$ denotes the subgraph induced by $V_1$ and $\delta(G(V_1))$ denotes the minimum degree of graph $G(V_1)$. Prove this decision problem is NP complete.

I'm trying to prove $$PARTITION \le_p This-Problem$$ but haven't came up with a solution until now. I've never met a problem dealing with the minimum depth of a graph. Is there any theorem about it? Could anyone help me out here?