Cheapest spanning tree

Question

I am trying to prove the following:

Let $x_1$ be any vertex of a weighted connected graph $G$ with $n$ vertices and let $T_1$ be the subgraph with the one vertex $v_1$ and no edges. After a tree (subgraph) $T_k$, $k<n$, has been defined, let $e_k$ be a cheapest edge among all edges with one end in $V(T_k)$ and the other end not in $V(T_k)$, and let $T_{k+1}$ be the tree obtained by adding that edge and its other end to $T_k$. Prove that $T_k$ is a cheapest spanning tree in $G$.

My plan is as follows: Fix an order $\triangleleft$ of the edges of $G$, and order the edges according to the lexicographical order induced by $\triangleleft$ and the cost order; that is, $e_1\lt e_2$ if either $c(e_1)\lt c(e_2)$ or $c(e_1)=c(e_2) \land e_1\triangleleft e_2$. Then show that $T_n$ has the property that each edge $e$ of $T_n$ has ends in different components of $G_e$ where $G_e$ is the graph with the vertices of $G$ and the edges $\lt e$. Then to show that any spanning tree with this property is minimal.

What I cant show is that $T_n$ has this property.

Any help will be appreciated.

Thanks

Answer 1

Here is another way to prove the claim (not using the hint provided) :

Note $x_1 \ldots x_n$ the sequence of vertices added to build $T_n$ and note $e_k$ the edge joining $T_k$ to $x_{k+1}$.

Let $T$ be any spanning tree of $G$ and let $k$ be the greatest integer such that $T_k$ is a subtree of $T$. We show that $T$ is more costly than $T_n$ by backwards induction on $k$ :

If $k=n$ then $T = T_n$, so $c(T) \ge c(T_n)$.

If not, let $e$ be the first edge in the path in $T$ connecting $T_k$ to $x_{k+1}$. (it has one end in $T_k$ and the other end outside $T_k$, and there is a path from that other end to $x_{k+1}$ in $T$ not going through $T_k$)

Removing $e$ from $T$ and adding $e_k$ yields another spanning tree $U$ containing $T_{k+1}$. (it has the right number of edges and is still connected)

By induction hypothesis, $U$ is more costly than $T_n$, and by construction of $T_n$, $c(e) \ge c(e_k)$, thus $$c(T) = c(U) - c(e_k) + c(e) \ge c(U) \ge c(T_n)$$

Answer 2

This is false. Consider a cyclic graph in which all edges but one have equal weight and the one edge $b$ has lower weight. Then $G_e$ for edge $e\ne b$ includes only $b$, and thus all edges $e\ne b$ have the property that the ends of $e$ are in different components of $G_e$. But the edges $e\ne b$ form a non-minimal spanning tree.

I suspect you either want $\le$ in the definition of $G_a$, or you're missing the premise that all edge weights are different.

[Update:]

Brian's answer gave me the right idea how the proof I had in mind could be made to work with minimal changes – it's enough to arbitrarily break the ties between edges of equal weight. So fix some order $\triangleleft$ of the edges of $G$, and order the edges according to the lexicographical order induced by $\triangleleft$ and the cost order; that is, $e_1\lt e_2$ if either $c(e_1)\lt c(e_2)$ or $c(e_1)=c(e_2) \land e_1\triangleleft e_2$.

Then any spanning tree $T_n$ with the property that each edge $e$ of $T_n$ has ends in different components of $G_e$, the graph with the vertices of $G$ and the edges $\lt e$, is a minimal spanning tree.

For take any minimal spanning tree $T$ and add an edge $e$ of $T_n$ to it. Now it contains a cycle. The greatest (according to $\lt$) edge $g$ of this cycle isn't in $T_n$ (since all of the cycle except $g$ is in $G_g$), and its cost is that of $e$: not less since $g$ is the greatest edge in the cycle, and not greater since $T$ is minimal. Thus we can add edges of $T_n$ and remove edges not in $T_n$ one by one, thus transforming $T$ into $T_n$ without changing the cost.

Answer 3

Here’s the original problem, copied from van Lint & Wilson:

Let $x_1$ be any vertex of a weighted connected graph $G$ with $n$ vertices and let $T_1$ be the subgraph with the one vertex $v_1$ and no edges. After a tree (subgraph) $T_k$, $k<n$, has been defined, let $e_k$ be a cheapest edge among all edges with one end in $V(T_k)$ and the other end not in $V(T_k)$, and let $T_{k+1}$ be the tree obtained by adding that edge and its other end to $T_k$. Prove that $T_k$ is a cheapest spanning tree in $G$.

And here’s their hint:

One approach is as follows. Show that $T_n$ has the property that for each of its edges $a$, $a$ has ends in different components of $G:\{e\in E(G):c(e)<c(a)\}$. Then show that any spanning tree $T$ with this property is a cheapest spanning tree.

(If $E$ is a subset of the edges of $G$, $G:E$ is their notation for the graph with the same vertex set as $G$ and edge set $E$.)

Note that the algorithm in the problem works correctly on joriki’s example: as soon as one end of $b$ is included in some $T_k$, $b$ will be the next edge chosen, and this must happen for some $k<n$. The problem, therefore, must lie with the hint.

Note that $T_n$ actually has the following slightly stronger property, which joriki’s example does not: its edges can be ordered $e_1,e_2,\dots,e_{n-1}$ in such a way that $$\begin{align*} &(1)\qquad c(e_1)\le c(e_2)\le\dots\le c(e_{n-1})\text{ and}\\ &(2)\qquad \forall k<n\Big(e_k\text{ has ends in different components of }G_k\Big), \end{align*}$$

where $G_k$ has the same vertices as $G$ and edge set $$\{e\in E(G):c(e)<c(e_k),\text{ or }e=e_i\text{ for some }i<k\}\;.$$

Let $T_n$ be any spanning tree with this stronger property, and suppose that $T$ is a spanning tree with edges $a_1,\dots,a_{n-1}$ ordered so that $$c(a_1)\le\dots\le c(a_{n-1})\;;$$ I claim that $c(e_k)\le c(a_k)$ for $k=1,\dots,n-1$, from which it follows immediately that $T_n$ is minimal-cost.

If not, let $k$ be minimal such that $c(e_k)> c(a_k)$. Then $a_1,\dots,a_k$ are all in $G_k$, and for $k<i<n$ the graph $G_i$ must include all of the edges $a_1,\dots,a_k,e_k,\dots,e_{i-1}$. The edges $a_1,\dots,a_k$ are independent, so $G_k$ has at most $n-k$ components. The ends of $e_k$ are in different components of $G_k$, so $G_{k+1}$ has at most $n-k-1$ components, and by an easy induction $G_i$ has at most $n-i$ components for $k\le i<n$. But then $e_{n-1}$ has ends in different components of the connected graph $G_{n-1}$, which is absurd.