title: Verification algorithm for minimum vertex cover?
body: <p>We know that the minimum vertex cover is NP complete, which means that it is in the set of problems that can be verified in polynomial time. </p>
  
  <p>As I understand it, the verification process would require the following:</p>
  
  <ol>
  <li>Verify that the solution is a vertex cover at all</li>
  <li>Verify that the solution is the smallest possible subset of the source graph that satisfies condition #1</li>
  </ol>
  
  <p>I'm finding it hard to establish that step #2 can be done in polynomial time.  Can anyone explain how it is?</p>