Comment by contravariant

Wouldn't the size of the graph grow something like $n^k / k!$ ? This is not polynomial in $k$.