Prove that $L=\left\{ \left\langle G,k\right\rangle \mid G\mbox{ contains a vertex of degree at least }\log_{2}|V|\mbox{ or a clique of size }k\right\}$ is in $P$ ($G$ is undirected graph and $k$ is a positive integer).
I tried to understand how does the $log$ criteria makes the problem easier than $CLIQUE$. I mean, assume that all the vertices have degrees $<\log_2 |V|$. Therefore the sum of all the degrees $<|V|\cdot \log _{2} |V|$. The sum of all the degrees equal to $2|E|$ therefore $2|E|<|V|\cdot 2\log _{2} |V|$. I thought this fact might help, but I can't see how excatly.
Need some hint..