I saw a proof by Saeed Amiri, We will add one extra vertex v to the graph G and we make new graph G′, such that v is connected to the all other vertices of G. G has a Hamiltonian cycle if and only if G′ has a Wn+1. It is easy to check that if G has a Hamiltonian cycle then G′ has a Wn+1 wheel (just set v as a center). On the other hand, if G′ has a Wn+1 then there are two possibility:
v is the center of Wn+1→G has a Hamiltonian cycle. Another vertex u is the center of Wn+1 in G′. So both deg(u)=deg(v)=n. Then we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility. P.S1: By Wn I mean the wheel with n vertex.
P.S2: In this proof we say if we fix k=n+1 (size of the artificial graph), then the problem is NP-Complete in this restricted version, So it's also NP-Complete in the case k is as input parameter.
The proof is valid one way. If a graph has a hamiltonian cycle adding a node to the graph converts it a wheel. If the graph of k+1 nodes has a wheel with k nodes on ring. It has a hamiltonian cycle. BUT IF THE GRAPH OF N nodes has a wheel of size k. Then identifying which k nodes cannot be done in polynomial time. Thus the reduction cannot be done in polynomial time.