Except that O(|V|^2 log|V|) is still polynomial.<p>(|V| &#62; log|V|), therefore (|V|^2 |V| == |V|^3) &#62; (|V|^2 log |V|).  As a polynomial is a (loose) upper-bound, it cannot be greater than polynomial time, thus !NP-Complete.