For a simple and undirected graph $G$, is there a known upper bound on the number of edges it has, given number of vertices $n$, girth $g$ and maximum degree $\Delta$?


No, there is no bound. For instance, consider an $n\times n$ square grid. It has girth $g=4$ and maximum degree $\Delta=4$ but there are roughly $2n(n+1)$ edges, which is unbounded as $n\to\infty$ (even though the girth and maximum degree are bounded.

Question was edited to include number of vertices, but now there is a trivial bound: $e\leq n\Delta/2$, since the total number of edges is half the sum of the vertex degrees.

  • $\begingroup$ But, what about the case when the number of vertices are fixed? $\endgroup$ – user7952 Jul 16 at 8:10
  • $\begingroup$ Generally it is not advised to substantially edit a question after answers have been posted... $\endgroup$ – pre-kidney Jul 16 at 9:42
  • $\begingroup$ The upper bound is trivial and does not incorporate the girth information! $\endgroup$ – user7952 Jul 16 at 10:03
  • $\begingroup$ @user7952 you asked for a bound. With your initial givens, there was no bound (as I pointed out). Then you added another given and the bound became trivial. I have answered both your questions, and you have changed the goalposts both times. I believe this thread can be closed and based on the insights you can ask a new question that captures the essence of what you are looking for. The onus is on the questioner to ask what they mean, rather than to have the responder guess what the questioner really meant to ask. $\endgroup$ – pre-kidney Jul 19 at 5:18

You should have a look at this survey, section 4, you should be able to find some results.

A first upper bound, without taking into account $\Delta$ would be, for odd girth, $$\textrm{ex}(n, \{C_3, C_4, \dots, C_{2k}\}) < \frac{1}{2} n^{1 + 1/k} + \frac{1}{2} n,$$

Where $\textrm{ex}(n,H)$ is the maximal number of edge in a graph not including $H$.


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.