Let us show how we can apply this to the vertex cover problem. We have rewritten the dual formulation for the vertex cover problem. We have indicated by d(u) as the set of edges that have one endpoint in u. The dual formulation consists in maximising the sum of the y(e), while the sum of the y(e) for all the edges that are incident to a vertex u is less equal to the weight of vertex v.

---