all.
I have some question about proving NP-complete
The conditions of proving problem is NP-complete is following.
1) Problem is in NP
2) Problem is reducible other from NP-Complete Problem (Ex. SAT)
To do condition #1, we use certificate.
My question is this.
When we do certificate, I need to give C(Instance, string of suitable answer). For example, when I certificate Vertex Cover, I need to Instance of V.C (graph, and integer number k which is number of needed cover vertex), and string(the answer)
In this condition, can I give any Instance & k & string? The most simplest example can be done? and its result is "yes". what does it mean "yes"?
To prove that a problem is in NP, you do not need to provide an actual solution. You just need to prove that the certificate can be verified in polynomial time.
In your example, a "certificate" would be a set of k vertices, $S=\{v_1, v_2,...,v_k\}$. You do not need to actually specify what these k vertices are.
A simple graph (i.e. no repeated edges) with n vertices has at most $n^2$ edges $(v_i, v_j)$ for $i, j=1..n$ and $i \neq j$.
To verify the certificate, you just need to check that for each edge $(v_i, v_j)$ that at least one of $v_i$ or $v_j$ is in $S$. Since S has k elements, you should be able to do this in $kn^2$ comparisons or $O(n^3)$ which is polynomial time.