Are there more connected or disconnected graphs on n vertices? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T18:51:33Z http://mathoverflow.net/feeds/question/44877 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices Are there more connected or disconnected graphs on n vertices? Leonid Petrov 2010-11-04T21:16:29Z 2010-11-06T10:34:00Z <p>Suppose we are talking about graphs with \$n\$ labeled vertices. Which graphs are more common: connected or non connected?</p> http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44884#44884 Answer by Tony Huynh for Are there more connected or disconnected graphs on n vertices? Tony Huynh 2010-11-04T22:27:57Z 2010-11-05T11:24:26Z <p>I like Jonah Ostroff's proof, but here is an inductive proof (for the heck of it).</p> <p>Let \$c(n)\$ and \$d(n)\$ respectively denote the number of connected and disconnected graph on \$n\$ vertices. </p> <p>Evidently, \$g(n):=c(n)+d(n)\$ is the number of graphs on \$n\$ vertices. As Jonah Ostroff points out \$c(4)=38\$ and \$d(4)=26\$.</p> <p>So, inductively assume that \$c(n) > d(n)\$, let \$G\$ be a graph with vertex set \$[n]\$ and consider a new vertex \$n+1\$. If \$G\$ is connected, then adding any non-empty subset of edges incident to \$n+1\$ maintains connectivity. On the other hand, if \$G\$ is disconnected, then adding all edges incident to \$n+1\$ results in a connected graph.</p> <p>Therefore,</p> <p>\[ c(n+1) \geq (2^{n}-1)c(n)+d(n) = (2^n-2)c(n) + g(n). \]</p> <p>By induction, we have \$c(n) > g(n)/2\$. Substituting yields</p> <p>\[ c(n+1) > 2^{n-1} g(n)=g(n+1)/2. \]</p> http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44889#44889 Answer by Jonah Ostroff for Are there more connected or disconnected graphs on n vertices? Jonah Ostroff 2010-11-04T22:53:32Z 2010-11-04T22:53:32Z <p>Connectedness wins, since the complement of any disconnected graph is connected.</p> <p>EDIT: Perhaps you'd like a proof of this. Let G be a disconnected graph, G' its complement. If v and u are in different components of G, then certainly they're connected by an edge in G'. And if they're in the same component of G, then there's some w in another component (since G was disconnected), so v-w-u is a path in G'.</p> http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44890#44890 Answer by zhoraster for Are there more connected or disconnected graphs on n vertices? zhoraster 2010-11-04T23:01:26Z 2010-11-04T23:01:26Z <p>Connectedness wins by a knockout: the proportion of disconnected graphs is about \$n2^{-n+1}\$. See Flajolet, Sedgewick "Analytic Combinatorics", p. 138.</p> http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/44908#44908 Answer by Andreas Blass for Are there more connected or disconnected graphs on n vertices? Andreas Blass 2010-11-05T01:28:45Z 2010-11-05T01:28:45Z <p>For large \$n\$, not only are the vast majority of graphs on \$n\$ vertices connected, the vast majority have diameter 2. That is, any two vertices have a neighbor in common. (The standard reference for properties of most graphs on \$n\$ vertices, for large \$n\$, is the book "Random Graphs" by Bela Bollobas.)</p> http://mathoverflow.net/questions/44877/are-there-more-connected-or-disconnected-graphs-on-n-vertices/45029#45029 Answer by sleepless in beantown for Are there more connected or disconnected graphs on n vertices? sleepless in beantown 2010-11-06T04:57:40Z 2010-11-06T10:34:00Z <p>I like Jonah Ostroff short and sweet proof, but the key to it lies in the fact that there is not a bijection between the set \$S_1\$ of connected graphs and the set \$S_2\$ of disconnected graphs over \$n\$ labeled vertices for \$n \ge 4\$, as follows:</p> <ul> <li><p>the complement of each disconnected graph is a connected graph (which Ostroff points out)</p></li> <li><p><strong>the complement of a connected graph can also be a connected graph</strong></p></li> <li><p>thus the cardinality of the set of connected graphs must be larger than the cardinality of the disconnected graphs, because while there is a one-to-one mapping of each disconnected graph onto a connected graph, there exist connected graphs which do not map to a disconnected graph</p></li> </ul> <p>For example, for \$n=4\$:</p> <p>Take the \$12\$ possible un-drected Hamiltonian paths of length \$4\$ on a graph over four labeled vertices. </p> <p>The complement of each of these paths is also a hamiltonian path.</p> <p>Since we know that the complement of a disconnected graph is obviously connected for \$n>3\$, then the number of connected graphs is at least equal to the number of disconnected graphs. Hoewever, since for \$n>3\$, the complements of at least some of the connected graphs are also connected graphs, that means that there must be more connected graphs than there are unconnected graphs.</p> <p>The \$12\$ Hamiltonian paths are those connected graphs over \$4\$ vertices whose complements are also connect: thus the remaining \$2^6 - 12 = 52\$ graphs are divided into pairs of complement graphs which are connected and disconnected, </p> <p>yielding a total of \$26\$ disconnected graphs, and \$26+12=38\$ connected graphs over the set of \$64\$ labeled graphs over \$4\$ labeled vertices.</p> <p>The path graphs of length \$n\$ on the set of \$n\$ vertices are the canonical example of connected graphs whose complements are also connected graphs (for \$n>3\$).</p>