MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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.

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
wow, I didn't expect the bound to be so tight for separability. thanks for the example. – 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.

share|cite|improve this answer
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. – Alexey Kvashchuk Feb 6 '13 at 15:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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