I got confused about minimal and minimum in context of graph theory. Although, I have understanding that minimal means more than one minimum i.e. none qualifies as actual minimum so we say them minimal.

What exactly does minimal spanning tree mean? Also, what exactly does 'minimal edge' mean?

How do they differ from minimum spanning tree? How are 'minimal edge' different from minimum edge?

This doubt arose due to the statement:

S: There exists a minimum weight edge in G, which exists in every minimum spanning tree of G.

Can we say on using word 'minimum' it's implied that there is only one minimum weight edge. Besides, statement used "exists" which is singular.

  • 1
    $\begingroup$ Where did you encounter "minimal spanning tree" and "minimal edge"? This statement doesn't mention them. Minimum here means a global minimum: a tree/edge with the smallest weight (there is no other tree/edge with a smaller weight). $\endgroup$ – user114966 Mar 2 at 22:44
  • $\begingroup$ Today, here: link. Although, someone else pointed out too, but he seem to have deleted his comment. $\endgroup$ – sgoel Mar 2 at 22:47
  • $\begingroup$ @Dmitry, Sir, Does all edges with minimum weight qualifies as Global Minimum, or Do we say Global minimum in that case don't exist? $\endgroup$ – sgoel Mar 2 at 22:55
  • 1
    $\begingroup$ I agree with this answer: math.stackexchange.com/a/2142655/743044 . Note that "minimum" implies "minimal". So it's not incorrect to use "minimal" instead of "minimum", but no reason to do that. $\endgroup$ – user114966 Mar 2 at 22:55
  • $\begingroup$ All such edges are global minima. (I use word "global" only to stress that they are minima across the set of all edges) $\endgroup$ – user114966 Mar 2 at 22:57

A minimum weight edge is an edge whose weight is minimal among all edges. There can be more than one minimum weight edge. All minimum weight edges have the same weight.

Similarly, a minimum spanning tree is a spanning tree whose weight is minimal among all spanning trees. There can be more than one minimum spanning tree. All minimum spanning trees have the same weight.

In some cases, there is a distinction between minimum and minimal. For example, a minimum vertex cover is a vertex cover whose weight is minimal among all vertex covers. In contrast, a minimal vertex cover is a vertex cover, any proper subset of which isn't a vertex cover. Finding a minimal vertex cover is easy – start with the set of all vertices, and repeatedly remove a vertex as long as it is possible to do so while maintaining the property of covering all edges. In contrast, finding a minimum vertex cover is expected to be hard (the corresponding decision problem is NP-hard).

The same property of being minimal doesn't make much sense for edges and spanning trees. When people say minimal edge or minimal spanning tree, they probably mean minimum (weight) edge and minimum spanning tree.

  • $\begingroup$ Sir, I have a confusion, saying something is "minimum" only if it's unique minimal, Is that incorrect?link If graph have all edge weights same, it's bit inconvenient to say graph have all minimum weight edges. $\endgroup$ – sgoel Mar 3 at 12:07
  • $\begingroup$ You can use a word in any way you like, as long as everybody understands what you mean by the word. The standard definition of minimum doesn't imply uniqueness. $\endgroup$ – Yuval Filmus Mar 3 at 12:08
  • $\begingroup$ For example, the minimum value attained by the sine function is $-1$. It is not attained uniquely. $\endgroup$ – Yuval Filmus Mar 3 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.