US-EGMO-TST 2020 Problem 5

Let $G = (V, E)$ be a finite simple graph on $n$ vertices. An edge $e$ of $G$ is called a bottleneck if one can partition $V$ into two disjoint sets $A$ and $B$ such that

• at most $100$ edges of $G$ have one endpoint in $A$ and one endpoint in $B$ ; and
• the edge $e$ is one such edge (meaning the edge $e$ also has one endpoint in $A$ and one endpoint in $B$ ).

Prove that at most $100n$ edges of $G$ are bottlenecks.

Proposed by Yang Liu