Let $n$ be the minimum possible size of a 4-regular graph with girth $g$. Consider a graph with a minimum degree of at least four with girth $g$, can I say that the size of such graph must be at least $n$ (as each vertex has at least four neighbours, making the graph more denser than a 4-regular graph; hence, in order to obtain the same girth it requires more vertices) or there might be such a graph with size less than $n$?
Girth is the length of the shortest cycle in the graph.


1 Answer 1


No, you can't say that, unless you prove it to be true. The way to know what you can say is to try to prove it; if you can prove it, you can say it, otherwise you can't.

It is possible that offering more freedom in the permissible degrees for each vertex allows constructing a smaller graph, so you can't trivially infer the conclusion you wish for.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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