Prove that $GRAPHCONTRACTIBILITY = \{(G, H) | $ H can be obtained from G by sequence of edges contractions} is NP-complete. Contraction defines as follows: given edge $(v, u)$ replace it with a vertex, which neighbors are neighbors of $u$ or $v$.
My attempt. I want to reduce SAT to this problem. I need to construct a formula from given graph, such that if the formula is true, then the graph is contractable to the other. I have an idea that we can use edges for variables -- existing in the second graph are going to be ones, the others are going to be zeros. But it didn't work -- or I couldn't invent a good construction.