# Proof: How many edges need be removed from this graph to produce the spanning tree?

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

• The "easy proof" looks perfectly fine to me. – Manuel Lafond Nov 5 '14 at 2:41
• The easy proof is probably what you're supposed to do, but you first need to show $G$ is connected (it's not too hard to do that just from looking at the degree sequence in this case). – Casteels Nov 5 '14 at 19:27

For the proof, recall that if a connected graph on $n$ vertices has $n$ or more edges, the graph surely contains at least one cycle. Any edge can be removed from this cycle and the graph still remains connected. Repeat this process until only $n-1$ edges remain.