Euclidean Minimum spanning tree and an extra edge

Consider 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 which has edges. Now suppose we are required to use exactly edges and find the smallest length graph . Clearly, will contain exactly one cycle. Now suppose we remove the longest edge from this cycle and obtain graph . I am wondering if 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.

Re: Euclidean Minimum spanning tree and an extra edge

If we are given 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 . I will start with vertex and take the edge with maximum weight incident to . I then go to the vertex on the other side of the edge, call it and pick its largest edge not incident to . 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 , pick the edge incident to 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.

Re: Euclidean Minimum spanning tree and an extra edge

Re: Euclidean Minimum spanning tree and an extra edge

Thank you for clarifying.

So in other words, is the Traveling Salesman solution of on the points, and we take , where . In this case, I would use an exchange argument to transform into , the MST. Swap out edges from and such that the weight is non-decreasing from to . 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 is constructed by using an MST algorithm.

Does this help?

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. is not (necessarily) the solution to the TSP. The TSP requires every "city" to be visited exactly once. There is no such restriction for .

Re: Euclidean Minimum spanning tree and an extra edge

If a city isn't visited at all, then minus an edge cannot be an MST. Also, if you don't have the assumption that is connected, won't be a spanning tree.

Re: Euclidean Minimum spanning tree and an extra edge

Quote:

Originally Posted by

**macosxnerd101** If a city isn't visited at all, then

minus an edge cannot be an MST. Also, if you don't have the assumption that

is connected,

won't be a spanning tree.

Of course are all spanning graphs. What I meant earlier is that in , vertices can have degree greater than 2, but not so in the TSP solution. Therefore is not necessarily the TSP solution.

Re: Euclidean Minimum spanning tree and an extra edge

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

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

is an MST. I'd still go with the exchange argument to show that a sequence of edge swaps removing edges from

and replacing them with edges from

whose weights are at least as large as the ones removed from

will satisfy the minimality portion. Once you have connectivity and $n-1$ edges, you have a spanning tree.

The connectivity of the graphs is not an assumption. The graphs are all connected/spanning by construction. Note that contains exactly 1 cycle, and to get from , we remove the longest edge from the cycle. So there is no loss of connectivity.

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.

Re: Euclidean Minimum spanning tree and an extra edge

Re: Euclidean Minimum spanning tree and an extra edge

You should also explicitly define in your problem statement as: is the unique, connected graph that minimizes the total length among all graphs with edges over the given points.

Now- are the weights equal for and ? Yes. You prove it with an exchange argument. Are the graphs equal? Not necessarily. Remember- you can have multiple MSTs for a given graph.

Re: Euclidean Minimum spanning tree and an extra edge

Quote:

Originally Posted by

**macosxnerd101** Now- are the weights equal for

and

? 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 for almost all configurations? (The set of of configurations that have multiple MSTs has measure zero).

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 is a valid claim (specifying the constraint on the edge , of course). In other words, there exist an MST isomorphic to .

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 points in, say, , the MST will be unique.

If this is confusing, just assume that we are only interested in configuration of points for which are all unique.