Let $G$=$(V,E)$ with $V=$ {$1,2,...n$}  and $E$ = {$e_1$,$e_2$,...$e_m$}. On the set of edges we have a cost function $c : E  R$, with a property like if i $\neq$ j then c($e_i$) $\neq$ c($e_j$). We also know that the graph is represtend with adjancency lists, $A(v)$,v$\in$V, and for $u$ $\in$ $A(v)$, i can find the cost of the edge in O(1).What my exercise requires : I am given a function, which takes the graph $G$ and the function cost $c$. And it finds the set $T$ (which at begin is $empty$). How we obtain $T$? For every $v$ $\in$ $V$, i find the neighbor with the $minimum$ $cost$, the neighbor will be $u$. And in T i $add$ the edge $uv$ ($T  T  {vu}$).I need to prove that the graph $G'$=$(V,T)$ doesn't have circuits and the number of connected components is at most $n/2$.Thinking about the problem, i found a relation if the graph has a odd or a even number of vertex. The fact that we find for every $v$ $\in$ G, the neighbor with the minimum cost, means every vertex will have $at least$ one neighbor. Right? So we will have in $G'$ pairs like this, meaning we will have a lot of connected components with pairs which is at most $n/2$ cause of these pairs. Am I thinking right? But I have no idea how I could prove it a bit mathematically, not only in words.
Connected components at most n/2 problem
graph theory