Assuming your star is a single center vertex which is a vertex to all edges (like spokes in a wheel), then the optimal cover for all edges is 1, the central ver

Assuming your star is a single center vertex which is a vertex to all edges (like spokes in a wheel), then the optimal cover for all edges is 1, the central vertex. If you follow the algorithm, you will select two vertices and produce a covering, which is within a factor of two of the optimal. I remember proving this algorithm in class (a while ago). What I found interesting from Wikipedia is that this is the best known approximation, there is a proven lower bound of 1.363.