# Cheapest spanning tree

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

## 3 Answers

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)$$

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.

• Great -- I was hoping to complete my proof with some modification along similar lines but hadn't found the time to think about it properly -- your answer gave me exactly the right idea :-) (see the update to my answer). – joriki Jan 11 '12 at 5:41
• I tried to prove that this stronger property is satisfied by $T_n$ but failed. Can you be a little more explicit? Thanks. – Shahab Jan 12 '12 at 17:05

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.

• You are right! The problem is from here and the hint provided here(Problem 2C) (Dont know why they have messed up the problem numbers on the internet, it is not so in my book). Can you take a look at it and tell me what I am understanding wrong? – Shahab Jan 10 '12 at 10:17
• @Shahab: Your understanding is quite right; it seems to be the book that's in error. – joriki Jan 11 '12 at 5:37
• I think that you mean ‘(since all of the cycle except $g$ is in $G_g$)’, yes? – Brian M. Scott Jan 11 '12 at 5:49
• @Brian: Yes, thanks; fixed. – joriki Jan 11 '12 at 6:49
• I am not clear as to why such an ordering < would imply that each edge $e$ of $T_n$ has ends in different components of $G_e$. Can you be a little more explicit? Thanks – Shahab Jan 12 '12 at 17:04