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, 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). 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. 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
where $G_k$ has the same vertices as $G$ and edge set $\{e\in E(G):c(e)
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 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. But then $e_{n-1}$ has ends in different components of the connected graph $G_{n-1}$, which is absurd.