The problems have been carefully chosen for their pedagogical value, and hence might be similar to those given in past offerings of this course at UW, or similar to other courses at other schools. Using any pre-existing solutions from these sources, for from the web, constitutes a violation of the academic integrity you are expected to exemplify, and is strictly prohibited.
Most of the problems only require one or two key ideas for their solution. It will help you a lot to spell out these main ideas so that you can get most of the credit for a problem even if you err on the finer details. A final piece of advice: Start working on the problem sets early! Don't wait until the day (or few days) before they're due.
Two undirected graphs G=(V,E) and G'=(V',E') are isomorphic if there exists a bijection f from V to V' such that {u,v} is an edge of G if and only if {f(u),f(v)} is an edge of G'.The Subgraph Isomorphism problem is as follows: Given two graphs G and H, is G isomorphic to a subgraph of H?
Prove that Subgraph Isomorphism is NP-complete.
Consider two graphs G=(V,E) and H=(U,F). A homomorphism from G into H is a map f from V to U so that if {u,v} is an edge of G, then {f(u),f(v)} is an edge of H.The Graph Homomorphism problem is as follows: Given two graphs G and H, is there a homomorphism from G into H?
Prove that Graph Homomorphism is NP-complete.