MATHEMATICS : CUT SET

1. In a connected graph G, a cut-set is a set of edges whose removal from G leaves G disconnected, provided removal of no proper subset of these edges disconnects G.

A cut-set always "cuts" a graph into two. And hence reduces the rank of the graph by one.

2. If we partition all the vertices of a connected graph G into two mutually exclusive subsets, a cut-set is a minimal number of edges whose removal from G destroys all paths between these two sets of vertices.

3. Every edge of a tree is a cut-set.

4. Cut-sets are of great importance in studying properties of communication and transportation networks. We wish to find out if there are any weak spots in the network that need strengthening by means of additional telephone lines. We look at all cut-sets of the graph, and the one with the smallest number of edges is the most vulnerable.

5. Consider a spanning tree T in a connected graph G and an arbitrary cutest S in G.

Is it possible for S not to have any edge in common with T ?

The answer is NO. Otherwise, removal of the cut-set S from G would not disconnect the graph. Every cut-set in a connected graph G must contain at least one branch of every spanning tree of G.

6. Will the converse also be true? The answer is yes, In a connected graph G, any minimal set of edges containing at least one branch of every spanning tree of G is a cut-set.

7. Every circuit has an even number of edges in common with any cut-set.

8. An edge incident on a pendant vertex is one such example, i.e., an edge incident on a pendant vertex is a branch of every spanning tree, since only that edge is a link to that vertex. Thus such an edge alone in a set is itself a cut set.

Here EF is a branch of every spanning tree and thus taken as a set it becomes the cut set.

                   

9. A cut-set S containing exactly one branch of a tree T is called a fundamental cut-set with respect to T.

Every chord of a spanning tree defines a unique fundamental circuit, every branch of a spanning tree defines a unique fundamental cut-set.

The ring sum of any two cut-sets in a graph is either a third cut-set or an edge disjoint union of cut-sets. Hence, union of any two cut set may not necessarily give a third cut set. (This is just like union of two fundamental circuits, which will either give another circuit or will be just edge disjoint union).

There are two points, each one being converse of another and both are true–

• A chord which forms a fundamental circuit C in a spanning tree of a graph belongs to every fundamental cut set and only those fundamental cut sets which are formed by the branches in C.

• A branch which forms a fundamental cut set F with respect to a spanning tree of a graph belongs to every fundamental circuit and only those fundamental circuits which are formed by the chords in F.

eBay