Very Hard Proof!!!!!!

Surely if C* has every edge of G in it it can't but help touch every spanning tree - but regardless if it has every edge then it must contain all the egdes in the cutset?

Is that the proof?

Almost - you simply have to show two things - one completely trivial.

First the trivial one, the minimal cutset itself must be a spanning tree by definition.

Second if C* is only gauranteed to have one edge in common with each spanning tree. Think of a graph with say one edge to a vertex that splits three ways to three new vertices that then recombine to to one vertex that then go via a single edge to a final vertex.

So its spanning trees are say these edges, there are only three routes through this graph:

A-B1-C1-D, A-B2-C2-D and A-B3-C3-D

The Graph looks like this:

../B1-C1\
A-B2-C2-D
..\B3-C3/

It should only take a moment to realise there are 3 * 3 * 3 = 27 unique cutsets and only 3 spanning trees.

Now think C* must have at least one edge of all three spanning trees so its a cutset for three independent routes by simple observation.

But what if there are more than one route between a subset of verticies, could you choose an edgeset for C* that includes each spanning tree but not a cutset?

Obiviously if its a common link that is shared by all available routes e.g. the link D-E below

../B1-C1\
A-B2-C2-D-E
..\B3-C3/

then its a cutset, but if its not that link and it contains any member of all the remaining spanning trees is it still a cutset?

You have to play definitions here to see of course it is and why. If you reduce it to have at least one edge from every spanning tree you either have single shared edges that form an immediate cutset or a group of edges on individual spanning trees that collectively for a cutset.

You have to explain why (a proof by contradiction should quickly lead to a contradiction of a defintion giving you teh answer you seek)!

If you are still having troubles think of

...B1-C1
../........ \
A-B2-C2-D-E
..\...X...../
...B3-C3

So B2 is connected to not just C2 but C3 and B3 is connected to C2 and C3. So I have now given this graph two new spanning trees A-B2-C3-D-E and A-B3-C2-D-E

Can you select a group of edges form any spanning tree so as not to get a cutset?

Ignore D-E - that's an immediate cutset. So are A-B1 + A-B2 + A-B3 or C1-D or C2-D or C3-D.

Can you see where this is going?