Main observation No vertex can cover two edges of a matching The size of every vertex cover is at least the size of every matching:M<C .M=C indicates the optimality Possible Solution:Using Maximal matching to find Minimum vertex coverMain observation • No vertex can cover two edges of a matching • The size of every vertex cover is at least the size of every matching: |M| ≤ |C| • |M| = |C| indicates the optimality • Possible Solution: Using Maximal matching to find Minimum vertex cover