Cut Sets in graph

Question

Question: Number of cut sets possible  a tree with 10 vertices _________

My approach : Number of edges in a tree with 10 vertices = 9. Each of these can be considered as a cut set as deleting one edge necessarily disconnects the graph. Also any combination (I mean supersets) of these 9 edges also form a cut set. Thus, number of supersets possible with 9 edges = 2^9, and to exclude the possibility that no edge is selected I delete 1 from the result.

Thus the number of cut sets = 2^9 - 1 = 511.

But the answer is written 9. Apparently they are not considering the super sets. Why?

Comments

yes, given answer is right.If deleting a certain number of edges from a graph makes it disconnected, then those deleted edges are called the cut set of the graph.

In your question,

given that a tree with 10 vertices. in a tree number of edges=number of vertex-1.

So number of edges =9

Now in a tree, if we delete any edge then the resultant graph will be the dissconnected graph.So there are 9 possibilities to make graph disconnected.

---

if graph disconnected by simply one edge then why you are considering supersets of it.

you have to check only set of edges who are the cause of disconnected graph.

Answer 1

Cut set means, u cut an edge or more than one edge from the graph , and graph becomes disconnected

Like bridge is very good example of cut set. In a tree every edge is a cut set, because, if u delete 1 edge from the tree, then that vertices becomes disconnected.

Now when u taking superset, means for example, u are cutting 2 edges of the graph , an then graph becomes disconnected. And u r asking is it not a condition for disconnection?

Yes, obviously it is a disconnection, but it violates the definition of cutset (which tells u cut an edge from the graph which makes graph disconnected)

If u cut 2 or more edges and then graph becomes disconnected, then it could be a case, that it is not a tree.

That is why superset shouldnot take consideration of it

Comments

for superset , it is a cutset

but it is not for a tree because for vertex  say v1 , e1 is cut edge

If u want vertex v2 to be cut vertex, then cutedge will be e2 , and not e1

---

So, in short, we can define cut set as - "a cut set is a set of minimum number of edges whose removal disconnects the connected graph."

ryt??

---

yes sreshta is perfectly right ...

cut set is a set of edges whose removal makes the graph disconnected,provided no proper subset of these edges disconnects the graph