# Relation between digraph and NP-Complete problem

Can there be any relations regarding the number of nodes available in a digraph so that to qualify it as NP-Complete problem. If we consider this problem for instance:
Input: A digraph $G=(V,E)$ and two nodes $u,v \in V$
Question: Is there a path in $G$ from $u$ to $v$?
Can we say this problem is NP-Complete problem since the digraph have only two nodes that they have a path from one another and this makes it be a Hamiltonian Path.
Hints are appreciated!

• @FrankW the question part was is there a path in $G$ from $u$ to $v$ – fudu Mar 13 '14 at 14:08
• I still don't get what you want to know. The problem you describe is exactly Hamiltonian Path, which is NP-complete but does not restrict the size of the given graph. So where does "since the digraph have only two nodes" come from? And what is the relation to your first sentence? – FrankW Mar 13 '14 at 14:54
• @FrankW I had a wrong understanding that the number of nodes could affect the problem to be NP-Complete problem or not. Now I get the whole picture. :D – fudu Mar 13 '14 at 15:05
• I don't really understand the downvote. Sure, having properly understood the basics of complexity, this question doesn't come up, but it seems to me that this is a fair enough question to ask for someone who is just starting to learn the subject. – G. Bach Mar 13 '14 at 16:57

For example, the fact that 3-SAT is NP-complete doesn't mean that you would have any difficulty telling me whether the formula $(X\vee Y\vee Z)$ is satisfiable. In your example, you've observed that, for a graph with a single edge, that edge is a Hamiltonian path. That doesn't mean that it's hard to tell whether a graph has a single edge, or that it's easy to compute Hamiltonian paths on all graphs.