Skip to main content

"sparse graphs are locally tree-like"

I would like to be able to state with confidence that sparse graphs (graphs with small numbers of edges) are locally tree-like (they have few short cycles). Apparently "Sparse graphs are locally tree like in the sense that the typical size of loops is $O(N)$" - see citation below. Here I am pretty sure "$N$" is $|V|$, the number of nodes. But I can't find any proof or formal statement of this.

I am interested in "most" graphs, not all of them, so if my understanding is right this is not a question of extremal graph theory. For example, I would like to be able to say something like: if $|E| = O(|V|)$ then most graphs have girth $O(|V|)$, or most loops have length $O(|V|)$.

N. Macris, Applications of correlation inequalities to low density graphical codes, The European Physical Journal B - Condensed Matter and Complex Systems, 2006; or the arXiv version

user13038
  • 101
  • 1
  • 3