A covering C is any set of edges such that any vertex of the graph is an end-point of (at least) one edge of C. A minimum-cardinality covering is a covering with the smallest possible number of edges....

1. 
   

   
   A covering C is any set of edges such that any vertex of the graph is an end-point of (at least) one edge of C. A minimum-cardinality covering is a covering with the smallest possible number of edges.
   

   
   
   
   
   1. 
      

      
      A salesman ineducational toys has a selection of geometrical shapes (cubes, pyramids and so on), each of which is manufactured in a range of colours. He wishes tocarry with him a minimum number of objects so that each colour and each shape is represented at least QDce. Justify the following statement. The number of objects he must carry isequal to the number of elements in a minimum-cardinality covering in the graph where each shape and each colour are individually represented by a
      

      
      
   
   
   
   

single vertex and there is an edge joining a shape vertex to a colour vertex if that shape is manufactured in that colour.

1. 
   

   
   Let M be a maximum cardinality matching and C be a minimum cardinality covering of G = (V, E). Now construct:
   

   
   

1. 
   

   
   a covering C' from M by adding to M, for every unmatched vertex
   

   
   

v, one edge incident with v,

and

1. 
   

   
   a matching M' from C by removing from C,for every overcovered vertex v (that is, v is the end-point of more than one edge of C) all but one edge incident with C.
   

   
   

Show that:

and that

Hence deduce that C' is a minimum-cardinality covering and that M' is a maximum-cardinality matching. Thus the problem of finding a minimum-cardinality covering can be solved essentially by the maximum-cardinality matching algorithm of section 5.2.