Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.