Maximal number of bridges for a given vertex count and minimal degree For the problem statement below, what would be best way to prove it? I have a solution which I think is not very elegant which is why I am asking this question:

Prove that no graph on 100 vertices with every vertex of degree at least 2 has 96 bridges.

To extend this question, is it possible to give an upper bound on the number of bridges given $p$ and $d$ where $p =$ number of vertices in a graph and $d =$ minimum degree of each vertex? If yes, what is this upper bound?
Thanks.
 A: If a graph is not connected, we can increase the number of bridges by connecting two connected components by an edge. Thus a graph with the maximal number of bridges is connected. In a connected graph, the bridges form a tree connecting the connected components that would be left if all the bridges were removed.
In the present case, all the components at non-leaf nodes of the tree may be single vertices, but at the leaves of the tree this isn't possible since the single vertices would have degree $1$. A tree has at least two leaves, and the smallest possible component at the leaves of the tree that allows all vertices to have degree at least $2$ is a complete graph on $3$ vertices. Thus we must have at least $3$ vertices at each of the at least $2$ leaves of the tree of bridges, and at least $1$ vertex at each non-leaf node; thus, since there are only $100$ vertices, the tree of bridges has at most $96$ nodes, and thus at most $95$ bridges.
In the general case of $p$ vertices with minimum degree $d$, a node in the bridge tree that has degree at least $d$ in the bridge tree can be a single vertex, whereas a node of degree less than $d$ in the bridge tree needs to be a complete graph on $d+1$ vertices to allow all vertices to have degree at least $d$.
Let $b$ be the number of bridges. Then the bridge tree has $b+1$ nodes. The minimal number of vertices for given $b$ is attained if as many as possible of these $b+1$ nodes have degree at least $d$ in the bridge tree and thus don't require additional vertices. A tree with $b+1$ nodes can have at most
$$n:=\lfloor\frac{b-1}{d-1}\rfloor$$
nodes of degree $d$, so there are at least $b+1-n$ nodes with lower degree. Each of these requires $d+1$ vertices, whereas each of the $n$ nodes requires one vertex, so the total number of vertices is bounded from below by
$$
\begin{eqnarray}
v
&\ge&
(b+1-n)(d+1)+n
\\
&=&
(b+1)(d+1)-nd
\\
&=&
(b+1)(d+1)-d\lfloor\frac{b-1}{d-1}\rfloor
\;.
\end{eqnarray}
$$
Since we know how to construct a graph with exactly this number of vertices, the bound is tight. To obtain an almost tight bound on b in terms of $v$, we can bound the floor function:
$$
\begin{eqnarray}
v
&\ge&
(b+1)(d+1)-d\lfloor\frac{b-1}{d-1}\rfloor
\\
&\ge&
(b+1)(d+1)-d\frac{b-1-(d-2)}{d-1}
\\
&=&
(b+1)(d+1)-d\frac{b+1-d}{d-1}
\\
&=&
\frac{(b+1)(d^2-d-1)+d^2}{d-1}\;,
\end{eqnarray}
$$
and thus
$$
b\le\frac{(d-1)v-d^2}{d^2-d-1}-1\;.
$$
Substituting $d=2$ yields $b\le v-5$, in agreement with the previous result.
