Skip to main content
added 152 characters in body
Source Link
Aaron Meyerowitz
  • 30.3k
  • 2
  • 50
  • 106

I think you would need a condition something like $|E|<(1+(1-\epsilon)\ln(V))V$. If $|E|=3|V|$ then it could be that every vertex is on $6$ $3$-cycles. That is only one such graph but I would expect the girth would be low. In caseIf the graph is regular of degree $3$ (so $|E|=\frac{3}{2}|V|$ ) then every vertex is on a cycle of length shorter than $\log_2(V)$.

If I recall correctly, a random tree has expected diameter less than $4\sqrt{V},$ so the expected girth of a graph with $|V|=|E|$ would be $O(\sqrt{V}).$

I think you would need a condition something like $|E|<(1+(1-\epsilon)\ln(V))V$. If $|E|=3|V|$ then it could be that every vertex is on $6$ $3$-cycles. That is only one such graph but I would expect the girth would be low. In case the graph is regular of degree $3$ (so $|E|=\frac{3}{2}|V|$ ) then every vertex is on a cycle of length shorter than $\log_2(V)$.

I think you would need a condition something like $|E|<(1+(1-\epsilon)\ln(V))V$. If $|E|=3|V|$ then it could be that every vertex is on $6$ $3$-cycles. That is only one such graph but I would expect the girth would be low. If the graph is regular of degree $3$ (so $|E|=\frac{3}{2}|V|$ ) then every vertex is on a cycle of length shorter than $\log_2(V)$.

If I recall correctly, a random tree has expected diameter less than $4\sqrt{V},$ so the expected girth of a graph with $|V|=|E|$ would be $O(\sqrt{V}).$

Source Link
Aaron Meyerowitz
  • 30.3k
  • 2
  • 50
  • 106

I think you would need a condition something like $|E|<(1+(1-\epsilon)\ln(V))V$. If $|E|=3|V|$ then it could be that every vertex is on $6$ $3$-cycles. That is only one such graph but I would expect the girth would be low. In case the graph is regular of degree $3$ (so $|E|=\frac{3}{2}|V|$ ) then every vertex is on a cycle of length shorter than $\log_2(V)$.