Isn't an improper subset of edges of a cyclic graph, cyclic and thus not a minimum spanning tree?

Question

This is the formal definition of a minimum spanning tree taken from Algorithms by Dasgupta, Papadimitrious and U. Vazirani.

Input: An undirected graph $G = (V,E)$; edge weights $w_e$.

Output: A tree $T = (V,E')$, with $E' \subseteq E$, that minimizes $$ \operatorname{weight}(T) = \sum_{e \in E'} w_e. $$

My confusion arises from the fact that the edges in the minimum spanning tree are an improper subset of the edges in the original graph. If the graph were cyclic, then we would have removed the cycles in the minimum spanning tree and would have had fewer edges. How is it that we have an improper subset (containing all the edges of the original graph)?

This is the example given right before the definition and the graph clearly contains cycle edges.

Answer 1

It looks like you misread or misunderstand the standard set notation "$E'\subseteq E$".

That notation just means $E'$ is a subset of $E$, i.e. every element of $E'$ is also an element of $E$.

---

We do not speak of "an improper subset", most of the time if not ever.

Why?

Suppose $A$ and $B$ are two sets. $A$ is a subset of $B$ iff every element of $A$ is also an element of $B$. If, furthermore, $A$ is not $B$, then we say $A$ is a proper (or strict) subset of $B$.

If we want to mention "an improper subset" of $B$, what would it mean?

• It should mean $B$ itself. That is how I would understand that phrase upon first reading. Then, why do we want to say "an improper subset of $B$", a pretty long phrase, when we can just say "$B$", which is concise? The phrase "an improper subset" seems implying there are more-than-one such subsets for a given set, which is simply wrong.

• It could just means "subset" when it is used in distinction to "proper subset" (which sounds unnatural to me, but maybe that is only me). Again, why not just use "subset", which is concise?