Proving that problems are hard is a skill. But once you get the hang of it, reductions can be surprisingly straightforward and pleasurable to do. Indeed, the dirty little secret of NP-completeness proofs is that they are usually easier to create than explain, in the same way that it is often easier to rewrite old code than it is to understand and modify it.
I offer the following advice to those seeking to prove the hardness of a given problem:
Never try to use the general traveling salesman problem (TSP) as a source problem. Better, use Hamiltonian cycle, i.e. TSP where all the weights are 1 or . Even better, use Hamiltonian path instead of cycle, so you don't have to worry about closing up the path. Best of all, use Hamiltonian path on directed planar graphs where each vertex has total degree 3. All of these problems are equally hard, and the more you can restrict the problem that you are reducing, the less work your reduction has to do.
As another example, never try to use full satisfiability to prove hardness. Start with 3-satisfiability. In fact, you don't even have to use full 3-satisfiability. Instead, consider planar 3-satisfiability, where there is a way to draw the clauses as a graph in the plane such you can connect all instances of the same literal together without edges crossing. This property tends to be useful in proving the hardness of geometric problems. All these problems are equally hard, and hence NP-completeness reductions using any of them are equally convincing.
Don't be afraid to add extra constraints or freedoms in order to make your problem more general. Perhaps your undirected graph problem can be generalized into a directed graph problem and can hence be easier to prove hard. Once you have a proof of hardness for the general problem, you can then go back and try to simplify the target.
Selecting the right source problem makes a big difference in how difficult it is to prove a problem hard. Although theoretically any particular problem is as good as another, this is the first and easiest place to go wrong. When faced with trying to prove that a problem is hard, some people fish around through dozens of problems, looking for the one that seems the best fit. These people are amateurs; odds are they never will recognize what they are looking for when they see it.
I use four and only four problems as candidates for my hard source problem. Limiting them to four means that I can know a lot about each of these problems, such as which variants of these problems are hard and which are soft. My favorite problems are:
Many people are too timid in their thinking about hardness proofs. You are trying to translate one problem into another, while keeping the problems as close to their original identities as as possible. The easiest way to do this is to be bold with your penalties, to punish anyone for trying to deviate from your intended solution. Your thinking should be, ``if you select this element, then you have to pick up this huge set that prevents you from finding an optimal solution.'' The sharper the consequences for doing what is undesired, the easier it is to prove if and only if.
You should be asking yourself the following types of questions. ``How can I force that either A or B but not both are chosen?'' ``How can I force that A is taken before B?'' ``How can I clean up the things I did not select?'' After you have an idea of what you want your gadgets to do, you can worry about how to actually craft them.
Sometimes the reason you cannot prove hardness is that there exists an efficient algorithm to solve your problem! Techniques such as dynamic programming or reducing to polynomial-time graph problems such as matching or network flow sometimes yield surprising polynomial algorithms. Whenever you can't prove hardness, it likely pays to alter your opinion occasionally to keep yourself honest.