What's the difference between a Minimum Connecting Set and a Minimum Edge Cover?

315 Views Asked by At

A Minimum Connecting Set in my book is defined as The minimum number of edges which keep the graph connected. A Minimum Edge Cover is defined in my book as the minimum number of edges that cover all the vertices.

Aren't these two the same thing?

Can someone tell me where I'm going wrong please. Thanks guys!

2

There are 2 best solutions below

2
On BEST ANSWER

A set of edges can cover all vertices without yielding a connected graph.

For instance,

$$ u_1-u_2 \qquad u_3-u_4 $$ is not connected.

1
On

Take $K_4,$ the complete graph on $4$ vertices. Two edges will cover all the vertices, but it takes three edges to connect the graph. In $K_{100},$ $50$ edges are enough to cover the vertices, but you need $99$ edges to connect the graph. What made you think they were the same thing?