Minimal cuts vs Edge connectivity

747 Views Asked by At

Here is a question asking the connection between the edge connectivity of a graph and its minimal cuts.

As we know, the edge connectivity of an undirected graph is the minimum number k of edges that must be removed to disconnect the graph. For example, the edge connectivity of a tree is 1, and the edge connectivity of a cycle is 2.

My thought is that the capacity of the minimal cuts should be equal to the edge connectivity. Because a cut is to separate a graph into two disconnect parts. If we know the edge connectivity k, it means that we have to remove or cut off at least k edges to make the graph into two disconnect parts. Therefore the capacity of minimal cuts should be k.

I haven't found any conclusion or proof about this question, so I ask here. Could anyone check if my thought is correct or give me any other idea on it?

0

There are 0 best solutions below