# How to prove Dense Subgraph problem is in NP

I have been studying NP-Complete problems and I saw the Dense Subgraph problem. Then I saw that they are trying to show that the problem is NP (see below quote), but I can't understand how it verifies that time is polynomial.

Problem: Dense Subgraph

Input: A graph $$G$$, and integers $$k$$ and $$y$$.

Output: Does $$G$$ contain a subgraph with exactly $$k$$ vertices and at least $$y$$ edges?

To prove Dense Subgraph is NP-complete, we show that Dense Subgraph is in NP and is NP-hard by reducing CLIQUE problem to Dense Subgraph.

Dense Subgraph is NP: the polynomial time verifier will take $$(G,k,y)$$ and $$H = (V', E')$$ as certificate and check if $$H$$ is a subgraph of $$G$$, $$|V'| = k$$, $$|E'| \geq y$$.

The part of coming up with a polynomial verifier given a reasonable certificate (i.e., proof that the problem is in $$\mathsf{NP}$$) is usually easy, and left as an exercise for the gentle reader.