Skip to main content
2 of 3
tags and made link clickable and stabke, and added one; MJ not added on purpose
user avatar
user avatar

"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