I failed a graph theory exam last week and I would like to know how to solve some of the problems I got because I don't have any idea. One of the problems is:
Prove that, if for every instance of 3SAT problem we can decide in polynomial time complexity if it is satisfiable, then, for every bipartite graph we can decide in polynomial time complexity if it is Hamiltonian.
I don't even know how to start it. Could you help me with a proof for that, please?