0
$\begingroup$

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.

  • 1
    In case anyone else was also wondering: a [bridge](http://en.wikipedia.org/wiki/Bridge_(graph_theory)) is a cut-edge, i.e. an edge whose removal increases the number of connected components of the graph.2012-03-16

1 Answers 1

1

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.

  • 0
    @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?2012-03-17