Dense graph
Task number: 3965
Let \( G \) be any graph on \( 2n \) vertices, each its vertex has degree at least \( n \). Prove that \( G \) is edge \(n\)-connected.
Solution
If the graph is to be separated by removing several edges into components, at least one of the components will have at most \(n\) vertices. There are at most \( \binom{k}{2} \) edges between \( k \) vertices. The sum of degrees is \( kn \), so this component is connected by at least \( kn-2 \binom{k}{2} = k (n-k + 1) \) edges.
This function is concave on the interval \( [1, n] \), with minima at the extreme points when the number of outgoing edges is at least \( n \).
From the above we get that each edge cut must have at least \( n \) edges.
