2 1 previously the star graph has been shown to contain a hamiltonian cycle