Explain the correctness of an answer.

$1.)$ Consider the following problem: Given a graph G$($V$,$ E$)$ and numbers t and b$,$ the question is whether there is a set U of vertices of size t such that the number of edges between the vertices in U is at least b$.$ Show that this problem is in NPC$.$

$2.)$ Consider the following problem: Given a connected graph G$($V$,$ E$),$ the question is whether there is a connected subgraph G$($V$,$ E$)($containing all vertices$)$ such that G$$ has no cycles, and the maximum degree in G$$ is $2.$ Show that this problem is in NPC$.$ Note: A connected subgraph of G with no cycles is called a spanning tree.

$3.)$ Assuming that the $3-$coloring problem is in NPC$,$ show that the question of whether a graph can be colored with $4$ colors is in NPC$.$