Need help with the task above. I've solved it but I am not sure if I am right. My solution is:
To determine upper bound let's take complete $K_9$ and add one vertex in such a way we get a bridge. Hence our upper bound is 9*(9-1)/2 (number of edges in complete graph on 9 vertices) + 1 (bridge) = 37.
As for lower bound, let's take the subgraph of $K_9$ such that it contains minimum edges needed to remain connected. Then, applying the same logic as before, simply add one vertex and connect it to the graph. So number of edges will be: 9 (min connected subgraph of $K_9$) + 1 (bridge) = 10.
That sounds quite right to me but I am not sure. I would really appreciate if anyone could comment on my solution.
Assume graph is simple.
Suppose $br$ is a bridge, then $G\setminus br$ is union of two conected subgraphs $A$ and $B$ with $a$ and $b$ nodes.
Since there is only one bridge $A$ and $B$ must have a Hamilton cycle if $a,b\geq 3$. So the number of edges $e$ in $G$ is at least $a+b+1=n+1$ and it is easy to see that number is achivable. If $a=1$ or $b=1$ then $e=n$. Clearly $a=2$ or $b=2$ is not possible else we would have 2 bridges.
On the other hand $$e\leq {a\choose 2}+{b\choose 2} +1 \leq {n-1\choose 2}+1$$