Spanning tree created with cycles breaking different form the Maximal Spanning Tree.

Question

Let $G$ be a connected graph with $N$ nodes, $B$ the set of the nodes and $V$ the set of the edges of $G$.

For all edges $e \in V$, there is an associate positive weight $\nu_e > 0$ on this edge ($\nu_e=0$ if there is no connection). We suppose that there are no self-connecting edges (an edge that connects a node to himself) and that all the edges have different weigth.

It is very easy, using Kruskal or Prim's algorithm, to find a maximal spanning tree $T_{max} \subseteq V$ that is the spanning tree that maximizes the graph sum $$\sum_{e \in T_{max}} \nu_e.$$

Now, I want to operate on $G$ following this instruction :

• For every cycle $c$, I remove the edge of the cycle that have the most minimal weight (and I do nothing if this edge has already been removed before).

At the end of this simple algorithm, we get a spanning tree $T$ that covers every edges, and by definition of the maximal spanning tree we have :

$$\sum_{e \in T} \nu_e \leq \sum_{e \in T_{max}} \nu_e.$$

However, on all the examples I've tried, I always end up with both sums being equal... (I end up with $T=T_{max}$)

Is their a counter-example that would verify the following $$\sum_{e \in T} \nu_e <\sum_{e \in T_{max}} \nu_e.$$

Or maybe the tree $T$ constructed using this method has to be a maximal spanning tree ?

Any help or ideas are welcomed.

Answer 1

The tree you get this way is guaranteed to be a maximal spanning tree.

If $T_\max$ is a maximal spanning tree, and $C$ is any cycle, then $T_\max$ can't possibly include the minimal-weight edge $e$ of $C$. Suppose it did. Deleting $e$ leaves $T_\max$ in two components, and since $C$ contains at least one edge crossing from one component to the other (the edge $e$) it must contain at least two. So there's some other edge $e'$ lying on $C$ which crosses from one component to the other, and which we can add to $T_\max - e$ to make it connected again.

But this is an improvement: we've deleted $e$, and added $e'$ which has higher weight than $e$. This contradicts our assumption that $T_\max$ was a maximal spanning tree.

As a result, $T_\max$ already can't include any minimal-weight edge of any cycle. If we go through the cycles and delete their minimal-weight edges, we never lose any edges of $T_\max$, so the remaining subgraph must contain $T_\max$. However, the remaining subgraph is a tree (it doesn't have any cycles, we ensured that) and so it must be $T_\max$.

Answer 2

Let $e_1, e_2,\dots,e_m$ be an ordering of the edges such that $\nu_{e_1} \leq \nu_{e_2} \leq \dots \leq \nu_{e_m}$. If you run Kruskal's algorithm according to this ordering, the edges of the tree you get will be precisely those $e_i$ which are not in a cycle in the subgraph $G_i = (B, \{e_j, j \geq i\})$ of $G$. (Equivalently, those $e_i$ whose endpoints lie in different connected components of $G_{i+1}$.) On the other hand, your algorithm will delete those edges $e_i$ which are in a cycle in $G_i$. So the two algorithms actually give the same spanning tree!

Although this might not be useful to you right now, I can't resist adding a note about this question from the point of view of matroid theory. The above observations actually work in any matroid to show that your algorithm gives a maximum weight basis. There is actually a deeper underlying reason for this. The complement of a maximum weight basis is a minimum weight basis in the dual matroid. So running the greedy algorithm in the dual matroid to find a minimum weight basis and then taking the complement gives a maximum weight basis in the original matroid, and this is exactly what your algorithm does!