MO640 - Multiple Choice Question

Among the below alternatives, which one is correct?

1. Both problems (a) find a Hamiltonian Cycle and (b) find a Eulerian Cycle belong to NP-Complete class
2. Graphs with Hamitonian Cycle and Eulerian Cycle simultaneously do not exists
3. Eulerian and Hamiltonian Graphs are mandatorily connected
4. The Travelling Salesman problem is a particular case of the problem to find a Eulerian Cycle
5. NOA

Original idea by: Hiroshi Higa
Translation help by: Vitor Santos