I was wondering about the same thing. I can take you half step forward, but I still don't know the answer.

I've read a bit on wikipedia, which has this paragraph:

Cliques of fixed size -

A brute force algorithm to test whether a graph G contains a k-vertex clique, and to find any such clique that it contains, is to examine each subgraph with at least k vertices and check to see whether it forms a clique. This algorithm takes time O(n^k k^2): there are O(n^k) subgraphs to check, each of which has O(k^2) edges whose presence in G needs to be checked. Thus, the problem may be solved in polynomial time whenever k is a fixed constant. When k is part of the input to the problem, however, the time is exponential.[6]

So, I see why if k=constant the problem can be solved in polynomial time.

but here k = n-5 , which is still a function of n, so I'm still not sure why it's polynomial.

But maybe this helps a bit..

Can someone (staff / students) please clarify?