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.

Difficulty level: Moderate task
Proving or derivation task
Solution require uncommon idea
Cs translation
Send comment on task by email