# In Search of the Densest Subgraph
## 3 Measures of Graph Density and Associated Results
### Polynomial-Time Solvable Cases
#### 3.1.8 Subgraph with Maximum Edge-Connectivity  
The _edge-connectivity_ of a graph is the minimum number of edges that need to be deleted in order to disconnect it, it is denoted by \(\lambda(G)\). Since we only deal here with edge-connectivity (and not vertex connectivity), we call it simply _connectivity_. We call a graph \(k\)-connected if its connectivity is \(k\), i.e., \(\lambda(G)=k\). This also means the graph has a _cut_ (a set of disconnecting edges) of size \(k\), but no smaller cut. There are many results about graph connectivity. In particular, it can be computed in polynomial time, and a corresponding minimum cut can also be found in polynomial time (see, e.g., [PERSON] and Ibaraki (2000)).  
Here, we only focus on connectivity as a density measure. It is intuitive that a graph with high connectivity cannot be too sparse. For example, if it is \(k\)-connected, then each degree must be at least \(k\), since otherwise a node could be separated from the rest by less than \(k\) edges. The converse, however, is not true: if every degree is \(\geq k\), it alone may not make the graph \(k\)-connected (not even connected).  
It is reasonable to capture a highly connected community by a subgraph with high connectivity. Therefore, we consider the task of finding a subgraph that has the highest possible connectivity among all subgraphs of the given input graph. This and related questions were investigated by [PERSON] (2000). Here, we outline a simple algorithm to find a subgraph with the highest connectivity, assuming that a subroutine is available to find a minimum cut in any given graph. It is interesting that, while it may first appear hard to find the most connected subgraph among exponentially many subgraphs, the problem actually has a simple polynomial-time algorithm, once we can use a minimum cut finding subroutine.  
Principle of the Algorithm  
* Find a minimum cut in the input graph \(G\); let its size be denoted by \(k=\lambda(G)\).
* Let \(A\), \(B\) be the two node sets into which the minimum cut divides the graph. A key observation is that, if there is any subgraph \(G_{0}\) with \(\lambda(G_{0})>k\), then it must be either fully in \(A\) or fully in \(B\). This is because, if \(G_{0}\) had nodes on both sides, then the found cut of size \(k\) would separate these nodes, too. \(G_{0}\  
**Analysis:** At most how many minimum cut computations are needed?  
At first, it may not be obvious that the algorithm calls the minimum cut subroutine only polynomially many times. After all, the graph is repeatedly split into two parts by a minimum cut computation, and then the algorithm is recursively called for each part. This may give the impression that in the worst case we may make an exponential number of minimum cut computations, since we keep splitting each graph, and, therefore, keep doubling the number parts. This impression, however, is incorrect. Let \(f(n)\) denote the number of minimum cut computations we carry out when the recursive algorithm is run on an \(n\)-node graph.  
**Claim:**\(f(n)\leq n-1\).  
Proof.: We use induction. The base case \(n=1\) is trivial, since \(f(1)=0\), as no minimum cut computation is needed for \(n=1\). In the recursive step we partition the graph into two parts, let the number of nodes in them be \(k\) and \(n-k\). We do not know the value of \(k\) in advance, only that it is an integer between \(1\) and \(n-1\). Nevertheless, by the induction hypothesis, we can assume \(f(k)\leq k-1\) and \(f(n-k)\leq n-k-1\). The total number of minimum cut computations we make for \(n\) nodes is at most the sum of \(f(k)\) and \(f(n-k)\), plus one more to generate the split. Therefore, \(f(n)\leq f(k)+f(n-k)+1\leq(k-1)+(n-k-1)+1=n-1\). Observe that this holds regardless of the value of \(k\), thus it indeed completes the inductive proof.