# Euclidean Minimum spanning tree and an extra edge

• Apr 11th 2014, 11:50 AM
mnov
Euclidean Minimum spanning tree and an extra edge
Consider $n$ points randomly distributed in space. The goal is to find the graph that has the smallest Euclidean length that connects these points. The answer is clearly the minimum spanning tree $G_0$ which has $n-1$ edges. Now suppose we are required to use exactly $n$ edges and find the smallest length graph $G_1$. Clearly, $G_1$ will contain exactly one cycle. Now suppose we remove the longest edge from this cycle and obtain graph $G_1'$. I am wondering if $G_1' = G_0$ for any configuration of points. My intuition is that it is true, and I'm not able to find a counter example. However, I am not able to prove it. Can someone help?

Thanks.
• Apr 27th 2014, 12:53 PM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
If we are given $n$ randomly selected edges, we are not guaranteed that removing one such edge will produce a minimum spanning tree (note that there may be multiple MSTs for a graph). We are simply guaranteed that it is a spanning tree of minimal weight given the edges.

In Euclidean space, we can model the graph as $K_{n}$. I will start with vertex $v_{1}$ and take the edge with maximum weight incident to $v_{1}$. I then go to the vertex on the other side of the edge, call it $v_{2}$ and pick its largest edge not incident to $v_{1}$. I continue this process such that no vertex on an iteration picks an edge incident to a vertex selected from any previous iteration. We are left with a spanning tree. Now for $v_{n}$, pick the edge incident to $v_{1}$ and we have a cycle. Remove the edge on this cycle with the maximum weight. We have a spanning tree that is clearly not minimal.
• Apr 27th 2014, 05:11 PM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

If we are given n randomly selected edges, we are not guaranteed that removing one such edge will produce a minimum spanning tree (note that there may be multiple MSTs for a graph). We are simply guaranteed that it is a spanning tree of minimal weight given the edges.
The $n$ edges of $G_1$ are NOT randomly selected and neither is the removed edge (it is the longest edge that is removed). $G_1$ is the unique graph that minimizes the total length among all graphs with $n$ edges over the given $n$ points.
Once the configuration of points is given $G_0, G_1, G_1'$ are all unique (well to be more precise, the set of configurations that have non-unique $G_0, G_1, G_1'$ has measure zero).
• Apr 27th 2014, 06:55 PM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
Thank you for clarifying.

So in other words, $G_{1}$ is the Traveling Salesman solution of $K_{n}$ on the $n$ points, and we take $G_{1} \setminus e$, where $e = max \{ w(e) : e \in E(G_{1}) \}$. In this case, I would use an exchange argument to transform $G_{1}^{\prime} = G_{1} \setminus e$ into $G_{0}$, the MST. Swap out edges from $G_{1}^{\prime}$ and $G_{0}$ such that the weight is non-decreasing from $G_{1}^{\prime}$ to $G_{0}$. If you are familiar with the proof of correctness of Kruskal's algorithm, the portion proving that the spanning tree is minimal does so using such an exchange argument.

A bit of intuition as well. The Held-Karp algorithm is the most efficient algorithm to compute the TSP solution. It operates by examining each vertex. For each vertex, it looks at the two lowest-cost edges and adds them up. The vertex with the lowest sum from this analysis is pulled out and its two lowest weight edges are chosen. We then compute an MST on the graph, limiting degree 2 on each vertex. Finally, we connect the two vertices of degree 1 after the MST algorithm terminates. So the intuition is that $G_{1}$ is constructed by using an MST algorithm.

Does this help?
• Apr 27th 2014, 07:44 PM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

So in other words, G_{1} is the Traveling Salesman solution of K_{n} on the n points,
No. $G_1$ is not (necessarily) the solution to the TSP. The TSP requires every "city" to be visited exactly once. There is no such restriction for $G_1$.
• Apr 27th 2014, 08:01 PM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
If a city isn't visited at all, then $G_{1}$ minus an edge cannot be an MST. Also, if you don't have the assumption that $G_{1}$ is connected, $G_{1} \setminus e$ won't be a spanning tree.
• Apr 27th 2014, 08:24 PM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
If a city isn't visited at all, then $G_{1}$ minus an edge cannot be an MST. Also, if you don't have the assumption that $G_{1}$ is connected, $G_{1} \setminus e$ won't be a spanning tree.

Of course $G_0, G_1, G_1'$ are all spanning graphs. What I meant earlier is that in $G_1$, vertices can have degree greater than 2, but not so in the TSP solution. Therefore $G_1$ is not necessarily the TSP solution.
• Apr 27th 2014, 09:10 PM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
Okay. That makes sense. You still need to assume connectivity to prove that $G_{1} \setminus e$ is an MST. I'd still go with the exchange argument to show that a sequence of edge swaps removing edges from $G_{1} \setminus e$ and replacing them with edges from $G_{0}$ whose weights are at least as large as the ones removed from $G_{1} \setminus e$ will satisfy the minimality portion. Once you have connectivity and $n-1$ edges, you have a spanning tree.
• Apr 28th 2014, 06:16 AM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
Okay. That makes sense. You still need to assume connectivity to prove that $G_{1} \setminus e$ is an MST. I'd still go with the exchange argument to show that a sequence of edge swaps removing edges from $G_{1} \setminus e$ and replacing them with edges from $G_{0}$ whose weights are at least as large as the ones removed from $G_{1} \setminus e$ will satisfy the minimality portion. Once you have connectivity and $n-1$ edges, you have a spanning tree.

The connectivity of the graphs $G_0, G_1 , G_1'$ is not an assumption. The graphs are all connected/spanning by construction. Note that $G_1$ contains exactly 1 cycle, and to get $G_1'$ from $G_1$, we remove the longest edge from the cycle. So there is no loss of connectivity.
• Apr 28th 2014, 07:13 AM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
That's good to know. So did you figure it out then from my suggestions about an exchange argument?

Also- in the future, I would suggest spelling out your assumptions in your question. I've been doing a lot of guessing at your assumptions because they weren't listed (such as connectivity), and you've been correcting them. Part of mathematics is specifying your definitions and assumptions quite clearly. You will get better help this way, too.
• Apr 28th 2014, 08:23 AM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
Also- in the future, I would suggest spelling out your assumptions in your question. I've been doing a lot of guessing at your assumptions because they weren't listed (such as connectivity), and you've been correcting them. Part of mathematics is specifying your definitions and assumptions quite clearly. You will get better help this way, too.

Thanks for pointing that out and sorry for the confusion. I should have explicitly stated that $G_1$ is connected (I thought it is obvious from the context). Anyway, here is a better version of the problem statement:

Consider $n$ points randomly distributed in space. The goal is to find the graph that has the smallest Euclidean length that connects these points. The answer is clearly the minimum spanning tree $G_0$ which has $n-1$ edges. Now suppose we are required to use exactly $n$ edges and find the smallest length connected graph $G_1$. Clearly, $G_1$ will contain exactly one cycle. Now suppose we remove the longest edge from this cycle and obtain graph $G_1'$. Is $G_1' = G_0$ for all configurations of the $n$ points?
• Apr 28th 2014, 08:29 AM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
You should also explicitly define $G_{1}$ in your problem statement as: $G_{1}$ is the unique, connected graph that minimizes the total length among all graphs with $n$ edges over the given $n$ points.

Now- are the weights equal for $G_{1}^{\prime}$ and $G_{0}$? Yes. You prove it with an exchange argument. Are the graphs equal? Not necessarily. Remember- you can have multiple MSTs for a given graph.
• Apr 28th 2014, 08:52 AM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
Now- are the weights equal for $G_{1}^{\prime}$ and $G_{0}$? Yes. You prove it with an exchange argument. Are the graphs equal? Not necessarily. Remember- you can have multiple MSTs for a given graph.

So $G_1' = G_0$ for almost all configurations? (The set of of configurations that have multiple MSTs has measure zero).
• Apr 28th 2014, 09:39 AM
macosxnerd101
Re: Euclidean Minimum spanning tree and an extra edge
I'm not an analyst and am not familiar with measure theory, sorry. If you can clarify what you mean by that, perhaps I can give a better explanation.

I think if you said that $G_{1} \setminus e \in \{ T : T is an MST of G\}$ is a valid claim (specifying the constraint on the edge $e$, of course). In other words, there exist an MST isomorphic to $G_{1} \setminus e$.
• Apr 28th 2014, 10:13 AM
mnov
Re: Euclidean Minimum spanning tree and an extra edge
Quote:

Originally Posted by macosxnerd101
I'm not an analyst and am not familiar with measure theory, sorry. If you can clarify what you mean by that, perhaps I can give a better explanation.

I meant that there exist multiple MSTs only for some carefully chosen configuration of points, for eg: arranging the points in a regular grid, etc. For a general distribution of $n$ points in, say, $[0,1]^2$, the MST will be unique.
If this is confusing, just assume that we are only interested in configuration of points for which $G_0, G_1, G_1'$ are all unique.