[math-fun] graphs with E edges
11 Nov
2013
11 Nov
'13
12:03 p.m.
CLAIM: The number of (isomorphism classes of) connected graphs -- indeed even merely the number of Eulerian graphs -- with E edges exceeds X^X where X=[1-o(1)]*E when E-->infinity. Also it is upper bounded by same, but now with X=[1+o(1)]*E. Also all this is valid for multigraphs (meaning you are allowed to have more than one edge joining two particular vertices). I recently proved this while doing something else. I have not seen it before but calling it "a new result in graph theory" is probably unjustified since proofs are easy enough that most anybody would probably rederive it when they needed it (?). Anyhow it can be proven in 1 page, and the proof is by no means unique.
4393
Age (days ago)
4393
Last active (days ago)
0 comments
1 participants
participants (1)
-
Warren D Smith