Assume the graph,$G$ has the degree sequence $6,4,4,3,3,3,3,2,2$. How many edges must be removed from $G$ to produce the spanning tree $T$?
We can construct this graph using Havel-Hakimi's algorithm. E.g:
$6,4,4,3,3,3,3,2,2$ is graphical(IG) iff $3,3,2,2,2,2,2,2$ IG iff $2,2,2,2,2,1,1$ IG iff $2,2,1,1,1,1$ IG iff $1,1,1,1,0$ IG iff $1,1,0,0$ and then we back track vertices easily and construct $G$ was graphed using this.
This has $15$ edges, and the spanning tree requires $1$ edge arriving at all vertices. So we can see that $2$ vertices aren't connected to the degree $6$ vertex, hence we require $6$ edges plus these $2$ connecting edges. So we have $8$ edges total. so $15-8=7$, so $7$ edges need be removed.
Question: Could I have just written: 'We have $9$ vertices, so we require $9-1=8$ edges to produce a spanning tree. We have $15$ edges, so we need remove $7$ edges.' Or was the full proof above required(are either valid/both valid/neither valid etc...)