# 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.

-
In case anyone else was also wondering: a bridge is a cut-edge, i.e. an edge whose removal increases the number of connected components of the graph. – joriki Mar 16 '12 at 20:29

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.

-
This solution is much nicer than mine. Thanks. Just one question though: When you say Thus we must have at least 2 vertices on each of the at least 2 leaves that don't form part of the tree of bridges; that leaves only 96 vertices to form the bridges, so there can be at most 95 of them.'' If we have 2 vertices on the "leaves" that don't form path of the tree bridges, then wouldn't they contribute to the bridges? Also we don't satisfy the the property that every vertex has degree 2. Shouldn't we say "... thus we must have at least 3 vertices ..."? Please correct me if I am mistaken. – mtahmed Mar 17 '12 at 1:19
@mtahmed: Sorry, I see now that that part was badly formulated. I've reformulated it to remove the ambiguity, and also to bring it in line with how I talk about the components later in the general case. I hope it's clearer now? – joriki Mar 17 '12 at 1:30