Give an example to show that the same conclusion does not follow if we allow some weights to be nonpositive

graph theory

I have the following question please.

Q: Argue that if all edge weights of a graph are positive, then any subset of edges that
connects all vertices and has minimum total weight must be a tree. Give an example
to show that the same conclusion does not follow if we allow some weights to be
nonpositive.

Attempt: to answer the counterexample part not the first, if we have a complete graph $K_3$ that is a triangle with all negative weights,
enter image description here

If we run Minimum spanning tree algorithms like prime and kruskals, we would get

enter image description here

Which is a MST.

However, the solution I got says the following:

To see that this conclusion is not true if we allow negative edge
weights, we provide a construction. Consider the graph $K_3$ 3 with
all edge weights equal to āˆ’1. The only minimum weight set of edges
that connects the graph has total weight āˆ’3, and consists of all the
edges. This is clearly not a MST because it is not a tree, which can
be easily seen because it has one more edge than a tree on three
vertices should have. Any MST of this weighted graph must have weight
that is at least āˆ’2.

Problem: why the minimum weight set of edges that connect a graph in this case is -3, which means it's not MST as it has a cycle please? Could we have the figure with 2 edges and weight -2 drawn above please?

Best Answer

The question didn't ask for a minimum spanning tree. It asked for a minimal subset of edges that included every vertex. This explicitly turns out NOT to be a tree if you allow negative weights.

Running an algorithm designed to make a tree is of course not going to give you a non tree!

Your tree is an example of a set of edges that connect all the vertices, with total weight -2. This is clearly not minimal as the whole graph has total weight -3.

Related Question