In a 2-connected graph find minimum no of edges

401 Views Asked by At

What is the minimum number of edges required for a $2$-connected graph?

I tried in this way:

We know that $\;\;\;\; \begin{align*} \kappa(G) \leq \text{ min-degree} \leq \frac{2\cdot e}{n} \end{align*} $ where $\kappa(G)$ is vertex connectivity. Therefore for $\kappa(G) = 2 \;\; $ we have $\;\; e \geq n$.

Is my argument valid?

Thanks !

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, your argument correctly shows that $e\geq n$. To complete the problem, you also need to give an example of a $2$-connected graph with exactly this number of edges, to show that you don't need more than $n$. (What you've done implies that such a graph must have every degree equal to $2$.)