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. Graph with degree sequence 6,4,4,3,3,3,3,2,2

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

  • 1
    $\begingroup$ The "easy proof" looks perfectly fine to me. $\endgroup$ – Manuel Lafond Nov 5 '14 at 2:41
  • $\begingroup$ 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). $\endgroup$ – Casteels Nov 5 '14 at 19:27

The graph shown is connected, has 9 vertices, and 15 edges. Remove edges from this graph, one by one, so that the graph remains connected and until no more edges can be removed without disconnecting the graph.

It can be shown that regardless of which edges are removed (and in which order these edges are removed), a minimal connected graph remains after exactly 7 edges are removed (since a spanning tree on 9 vertices has exactly 8 edges).

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy