The Gateway to Computer Science Excellence
+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 ?

in Graph Theory by Veteran | 345 views

1 Answer

+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...
by Boss
Ahh.. correct it was not sufficient. Thanks
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,218 questions
59,890 answers
118,128 users