# Proving that finding wheel subgraphs is NP-complete

Can you help me with this problem ?

Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W_{n}$ (a wheel $W_{i}$ is such that $i$ nodes form a cycle and a $i+1$st node is connected to all other nodes, resulting in $2i$ edges) is NP-complete.

• This object is also often referred to as the Wheel on $n$ vertices, and denoted $W_n$. – Pål GD Apr 23 '13 at 14:01
• @Raphael,Hamiltonian Cycle approach does not seems to be valid because for this problem one needs to show that finding certain SUBGRAPH is an NP-Complete problem. Hamiltonian Cycle does not deal with subgraphs... Any other ideas ? – 372 May 10 '13 at 21:03

Hint: Hamiltonian Cycle is $NP$-Complete.
Hamiltonian cycle does indeed look promising: note that $W_n$ contains a simple cycle.