Does anyone know if there is a result that relates a quantity such as an average degree to the fact the a (simple and connected graph) has no cut vertices?

e.g. if a graph has a Hamiltoninan cycle then it has not cut vertex. By Ore's theorem, if deg(v) >= n/2 for each vertex v (n is the number of vertices of a graph), then the graph is Hamiltoninan. Hence deg(v) >= n/2 implies no cut vertices (non-separable).

I am looking for a result similar to Ore's theorem, but w.r.t. non-separability e.g. something like if the deg(v) >= f(n) for each v (or some statement about the average degree), then the number of cut vertices is zero.

Thank you.


I do not think you can do anything better than $\frac{n}{2}$. Consider the following construction: Take two complete graphs of equal size $\frac{n-1}{2}$. Add one vertex $v$ and connect this vertex to all vertices of the two complete graphs. Each vertex has degree at least $\frac{n-1}{2}$ and this graph has a cut vertex.

  • $\begingroup$ wow, I didn't expect the bound to be so tight for separability. thanks for the example. $\endgroup$ – Alexey Kvashchuk Feb 6 '13 at 15:06

If you look for special graph classes, similar statements are possible, e.g., if each vertex of a self-complementary graph has degree at least two then the graph has no cut-vertex.

  • $\begingroup$ thank you. I am looking at a non-special case. Just a simple and connected graph. Given the example above I wonder if there are any other features (like Hamiltonian property) that imply non-separability. May be something in terms of, say, min/max degree (δ(G),Δ(G)). There are some results on the upper bound of the number of cut vertices in terms of δ(G)/Δ(G) but none are directly useful as I am interested in the case of zero cut vertices. $\endgroup$ – Alexey Kvashchuk Feb 6 '13 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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