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?