Reductions in What Direction?

Exercise 7.3

The problems of Satisfiability of Boolean formulas (\mathsf{SAT}) and of determining whether a given graph is Hamiltonian (\mathsf{HAM}) are two well-known \mathbf{NP}-complete problems.

The problem of determining whether a given graph contains an Eulerian circuit (\mathsf{EUL}) has a solution with cost \Theta(n + m), where n is the number of vertices in the graph and m is its number of edges.

Which one of the following sentences can we say it is true?

• \mathsf{SAT} reduces to \mathsf{HAM} and \mathsf{HAM} reduces to \mathsf{EUL}.
• \mathsf{EUL} reduces to \mathsf{SAT} and \mathsf{SAT} reduces to \mathsf{HAM}.
• \mathsf{SAT} and \mathsf{HAM} reduce to each other; \mathsf{EUL} only reduces to \mathsf{HAM}.
• \mathsf{SAT} reduces to \mathsf{EUL} and \mathsf{EUL} reduces to \mathsf{HAM}.