there's a short solution with induction on $n$ but i think this is a better way to think about the problem: We claim that $G$ has at most $100(n-1)$ bottlenecks. Suppose otherwise and let $G_0=G$. For $i=1,2,\dots, 100$, we will do the following: At each step, remove (all edges of) a spanning forest $F_i$ from $G_{i-1}$ to get another graph $G_i = G_{i-1}\backslash F_i$. Now, since $G_0$ had $>100(n-1)$ bottleneck edges, $G_{100}$ has at least one bottleneck $\overline{xy}$ left over. Since $x,y$ are still connected to each other, they must lie in the same connected component of each of $F_1,F_2,\dots, F_{100}$. Therefore we can find a path from $x$ to $y$ along each $F_i$, and all $100$ of these paths are edge-disjoint. This combined with edge $\overline{xy}$ yields $101$ edge-disjoint paths from $x$ to $y$, so it is impossible for $\overline{xy}$ to be a bottleneck, contradiction.

Posting for aesthetic purposes. I think this is by the problem author, not sure. Courtesy of v_Enhance for sharing it with me.

Featuring a motivational quote from the one and only Evan Chen: "Induction works unusually well on graph theory problems, often because a graph minus a vertex/edge is still a graph." Truly well said. Indeed, these are wise words from a wise man. Unfortunately, it took me many hours to understand these words of wisdom. We strong induct on $n$ with all the bottleneck edges of $G$ (so non bottleneck edges are removed). Note that the base case $n = 1$ obviously holds since there are $0 \leq 100$ edges. Suppose all graphs on $< k$ vertices have at most $100k$ bottlenecks. Now for the inductive step, suppose graph $G$ with $k$ vertices has some bottleneck $e$. Suppose that this bottleneck divides $G$ into two sets of vertices $G_1$ and $G_2$ with cardinalities $S_1$ and $S_2$ with $S_1 + S_2 = k$. By the problem, there are at most $100$ edges between $A$ and $B$. Furthermore, by inductive hypothesis, $G_1$ has at most $100S_1$ bottlenecks and $G_2$ has at most $100S_2$ bottlenecks, hence a total of at most\[100S_1 + 100S_2 + 100 = 100k + 100\]bottlenecks. But hey, that's not what we want. We want to show that there are at most $100k$ bottlenecks! This bound isn't tight enough. But also notice that the inequality in our base case is strict. So perhaps we can make a better bound than just $100n$? Let's try to prove the result for $100n - 100$. The base case still holds. If we use the same notation as above, we get at most\[(100S_1 - 100) + (100S_2 - 100) + 100 = 100k - 100\]bottlenecks. This in fact completes the inductive step and therefore our induction, so $100n - 100$ is actually the bound we want. So in fact, the result holds for the stricter bound of $100n - 100$, and we are done. $\blacksquare$ Remark: Wow, this problem was a real bottleneck for me.

Really nice! I have the same solution as tastymath. We prove a stronger bound of $100n - 100$. We use the following iterative procedure. Let $F_1$ be a maximal forest in $G$ (i.e. no other edges of $G$ can be added to $F_1$ without creating a cycle in $F_1$). Let $F_2$ be a maximal forest in $G\setminus F_1$, $F_3$ be a maximal forest in $G \setminus (F_1 \cup F_2)$, etc. until $F_{100}$. Let $vw$ be bottleneck which is not in $\bigcup_{i = 1}^{100} F_i$, and suppose there is no path between $v$ and $w$ in some $F_j$. We can then add $vw$ to $F_j$ while maintaining the fact that $F_j$ is a forest, contradicting maximality along with the fact that $vw \not\in \bigcup_{i = 1}^{100} F_i$. This implies that there is a path between $v$ and $w$ in each $F_i$, implying that there are $101$ disjoint paths between $v$ and $w$ (one path in each of the $F_i$, and the edge $vw$ as well). However, since $vw$ is a bottleneck, there is a partition $V(G) = V \sqcup W$ such that $v \in V$, $w \in W$, so that there at most $100$ cross edges between the two sets, meaning that there may be at most $100$ disjoint paths between $v, w$, a contradiction. Thus, all bottlenecks are edges of $\bigcup_{i = 1}^{100} F_i$, of which there are at most $100n - 100$. Done! $\Box$

The real short induction solution! The argument is by induction on $n$. The correct upper bound is $100(n-1)$. The base case is trivial. For the induction step, note a splitting along a bottleneck into graphs $A$ and $B$ implies there are at most \[100(|A|-1)+100(|B|-1)+100=100(n-1)\]bottlenecks, so done.

Lol what. I will prove the stronger bound of $100n-100$ by induction on $n$, with the base case of $n=1$ being obvious. Now if no edges of $G$ are bottlenecks, the claim clearly holds, so assume that a bottleneck exists. Pick any bottleneck, and note that when vertices (and the edges connected to them) are deleted, a bottleneck will remain a bottleneck unless, of course, it is deleted. Hence by deleting all of the vertices in $A$ we get that there are $100|B|-100$ bottlenecks completely in $B$. Similarly, there are $100|A|-100$ bottlenecks completely in $A$. So, by inductive hypothesis as $|A|,|B|<n$, there are at most: $$100|A|-100+100|B|-100+100=100(|A|+|B|)-100=100n-100$$bottlenecks of $G$, as desired. $\blacksquare$

dame dame

identical to tastymath's sol, posting for storage We claim a stronger bond of $100n-100$. Suppose FTSOC that there exist more bottlenecks. Define a "step" as an operation where we take a spanning forest of $G$ and remove all of its edges. After 100 steps, at most $100(n-1)$ edges are deleted, so there must still be a bottleneck $\overline{xy}$. They are obviously in the same connected component, and with each step, we deleted a path between $x$ and $y$, hence there exist $101$ disjoint paths between $x$ and $y$. This means that no matter how we partition the two sets, there will be $101$ edges connecting them as $x,y$ are in different sets, making it impossible for $\overline{xy}$ to be a bottleneck. Remark: somehow missed the easy induction sol, but this is way cooler so I'm not mad

I thought I did the problem incorrectly for like an hour since I kept getting the stronger bound. Here is a proof without induction. Call a set of at most $100$ edges in $G$ having one endpoint in $A$ and one endpoint in $B$ a "bottle". Let $S=\{ T_1, T_2, \ldots T_k \}$ denote the maximal possible set of disjoint spanning trees in $G$. Notice that if we remove all the trees in $S$ from $G$ then this disconnects the graph, but if we only remove some of the trees in $S$ from $G$ then the graph still has a spanning tree and is thus connected. Now, let $X_1,X_2, \ldots X_m$ be all the sets of bottles. If we let $t_\ell$ denote the number of edges of $X_\ell$ on a tree of $S$, then $t_\ell \geq k$ since each tree in $S$ needs at least one element of $X_\ell$ so that if we remove $X_\ell$ from $G$, it disconnects the graph. But, the total number of edges in all the trees of $S$ is $k(n-1)$. So, \[km \leq \sum_{i=1}^m t_i \leq k(n-1) \implies m < n \implies \sum_{i=1}^m |X_i| \leq 100m \leq 100(n-1) \]as desired. $\blacksquare$

A bit different idea. Take a bottleneck edge and remove it along with all of its accomplices. As a result, the graph becomes more disconnected! That is, the number of its connected components increases at least by one. Since the number of all connected components of a graph with $n$ vertices cannot exceed $ n,$ we can do this procedure at most $n-1$ times, deleting at most $100$ bottleneck edges each time. This means that after deleting at most $100(n-1)$ bottlenecks, no such edges will remain. We proved an even stronger estimate. The number of bottlenecks cannot exceed $100(n-1).$ Comment. More details on my blog.

This is the weirdest problem ever. We prove the bound $100n-100$ by strong induction on $n$. Notice that upon a partition of $V(G)$ into two valid sets $A$ and $B$, there are at most $100|A|-100$ bottlenecks among edges in $A$ and $100|B|-100$ bottlenecks among edges in $B$. So there are at most $100n-100$ bottlenecks in total, done. Remark. To phrase this solution non-inductively, one can just look at the number of connected components.