is shown to be NP-complete by Cheah and Corneil in 1990. This is basically an extension of the famous Hamiltonian cycle problem. Relaxing the regularity constraint leads to the connected f-factor problem. Given a graph G(V, E) and a function f : V → N, a connected f-factor of G is a connected spanning subgraph G′ such that d_G′(v)= f(v), ∀v ∈ V.
It is easy to extend the reduction by Cheah and Corneil to show that
connected f-factor problem is hard when the range of f is a fixed set.
We present the results on the how the complexity of, both the decision
and the optimization versions of the problem vary depending the nature
of f.