To show that $\Gamma(G)$ is connected, you need to be able to generate a path from $v$ to $u$ for any $v, u\in G$. Think of a step from $v$ as a multiplication of $v$ by some element in $S$. If you end up at vertex $w_1$ then you multiplied $v$ by $v^{-1}w_{1}\in S$. A path that takes you from $v$ to $u$ will look like: $v, w_1, w_2, ..., w_k, u$ and the multiplications that you did, in sequence were $$(v^{-1}w_{1})(w_{1}^{-1}w_{2})...(w_{k}^{-1}u)=v^{-1}u$$
The question then is, can you write $v^{-1}u$ as a product of elements in $S$? If $S$ generates $G$ then you can (for any $v^{-1}u\in G$). If there is any pair for which you cannot write such a product, i.e. a $v, u\in G$ so that there is no finite product of elements in $S$ that make $v^{-1}u$ then $S$ cannot generate $G$ since it cannot generate the element $v^{-1}u$.
It's always a spanning tree.
You probably already noticed this, but for completeness: the resulting graph is acyclic, because every cycle in the original graph has been destroyed. So we need to show that the result is still connected.
Another characterization of connectivity will be useful here: a graph $(V,E)$ is connected if and only if for every nonempty $S \subsetneq V$, there is a crossing edge: an edge between a vertex in $S$ and a vertex in its complement $V \setminus S$. So let's check this for the graph after deletions.
For a given set $S$, because our starting graph was connected, there are some crossing edges. Let $e$ be the lightest of these edges. I claim that the edge $e$ is never deleted, and so there is also a crossing edge in the graph we get at the end.
For $e$ to be deleted, we'd first have to find a cycle containing it. That cycle contains at least one vertex in $S$ and at least one vertex not in $S$. Following that cycle starting from $S$, at some point we leave $S$ - but then we have to come back to $S$ by a different edge. This can happen multiple times, but even if it only happens once, we see that the cycle contains at least two crossing edges: $e$, and some other edge $e'$ (and maybe others).
Since $e$ is the lightest crossing edge, it is in particular lighter than $e'$. So it is not the heaviest edge on this cycle, and will not be deleted when we consider this cycle. The same argument holds for every cycle containing $e$, so the edge $e$ will never be deleted.
In fact, the tree $T$ we get at the end is a minimum spanning tree.
To see this, take any other spanning tree $T'$. Let $e$ be an edge of $T$ not in $T'$. Adding $e$ to $T'$ creates a cycle, and deleting any edge of that cycle would create another spanning tree. Let's add $e$ and delete the heaviest edge of that cycle.
That heaviest edge is definitely not $e$, because $e$ is not the heaviest edge of any cycle. So we added $e$ to $T'$, then deleted an edge heavier than $e$. This means that we've reduced the total weight of $T'$: therefore, $T'$ is not a minimum spanning tree. Since some minimum spanning tree must exist, it can only be $T$.
Best Answer
In the Cayley graph, each of the edges corresponds to multiplication with one of the generators -- in one direction. In the other direction, the edge corresponds to multiplication with the inverse of that generator.
Thus, every edge can be traversed in either direction -- that's what the $\epsilon_i=\pm1$ exponents in the proof you show are for.
In other words, if you have a (simple) cycle in the graph, you can go around the cycle and keep track of what you're multiplying with -- and since by definition of cycle you end up where you started -- say, at element $b$ -- you have $$ ba_1^{\epsilon_1}a_2^{\epsilon_2}\cdots a_k^{\epsilon_k} = b $$ Canceling $b$ we get $$ a_1^{\epsilon_1}a_2^{\epsilon_2}\cdots a_k^{\epsilon_k} = e $$ The left-hand side is not forced to be $e$ by the group axioms (this would only be the case if we had $a_i=a_{i+1}$ and $\epsilon_i=-\epsilon_{i+1}$ for some $i$), and therefore the latter relation is impossible in a free group.