2

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?

jweyrich
  • 31,198
  • 5
  • 66
  • 97
Galaxy
  • 853
  • 2
  • 11
  • 28
  • 1
    Minimal in which sense? Cut the minimum number of edges to get two disjoint subsets? – jweyrich Oct 16 '15 at 00:25
  • 1
    @jweyrich Yes I think, since it's undirected graph in the question and no specific weights are assigned to the edges. – Galaxy Oct 16 '15 at 00:34
  • To my understanding, the concept of a cut is related to network problems, which means that in addition to the graph itself, a source node `s` and a terminal node `t` must be specified, and the notion is actually an `s`-`t`-cut; I assume that the notions are related, but not directly compatible. – Codor Oct 16 '15 at 18:53
  • @Codor Yes, it's related to network flow problem, since I found the edge connectivity can be determined by running Ford-Falkerson Algorithm, which is to find the maximum flow in a network. – Galaxy Oct 16 '15 at 22:14

0 Answers0