(1) Extra information so the correctness of an answer to a decision problem can be quickly checked. (2) For any graph property P and graph G, a certificate for G is a graph G' such that G has property P if and only if G' has the property.