1,287 views
2 votes
2 votes

For a regular graph how much large the value of degree (for each vertices) should be such that the graph is $2$ - connected. (vertex wise).

I did in this way :

$\begin{align*} &\quad \kappa(G) \leq \frac{2\cdot e}{n} \qquad \text{ where } \kappa(G) = \text{ vertex connectivity } \\ &\Rightarrow 2 \leq \frac{2\cdot e}{n} \\ &\Rightarrow n \leq e \\ &\Rightarrow n \leq \frac{\sum \left ( d_i \right )}{2} \\ &\Rightarrow n \leq \frac{n \cdot d}{2} \\ &\Rightarrow d \geq 2 \\ \end{align*}$

The above case can be realized by thinking of  a cycle graph of $n$ vertices.

But in the following case :

This graph is 3 regular and not 2- connected although $d \geq 2$ is satisfied.

Why this $d \geq 2$ is trivial and not working in some cases ?

1 Answer

2 votes
2 votes
the condition you have derived is necessary condition not a sufficient condition..

any regular graph which is 2-connected should have d>=2 but converse is not true...

Related questions

0 votes
0 votes
1 answer
1
Crime Master Gogo asked May 3, 2017
2,950 views
Is every k connected graph is k-1 connected or the reverse? I always get confused. Can someone explain with the help of an example.
0 votes
0 votes
0 answers
4