Suppose we are talking about graphs with $n$ labeled vertices. Which graphs are more common: connected or disconnected?

$\begingroup$ My question is clearly related to the uniform probability on the set of all graphs. Can this uniform measure be obtained from some known random graph model? However, this related subquestion is of much less interest for me now. $\endgroup$– Leonid PetrovNov 4 '10 at 21:17

1$\begingroup$ For 3 vertices, there is equality: 4 connected and 4 disconnected graphs. For 4 and higher, disconnected clearly wins out. Now, is that really what you need, or do you require a more specific answer (e.g. estimates), that's another problem... $\endgroup$– Thierry ZellNov 4 '10 at 22:26

4$\begingroup$ You mean connected clearly wins out, Thierry? For 4 vertices, 38/64 are connected. $\endgroup$– Jonah OstroffNov 4 '10 at 22:55

$\begingroup$ This is basically a duplicate of this question: mathoverflow.net/questions/13088/… $\endgroup$– Matthew KahleNov 6 '10 at 22:55
Connectedness wins, since the complement of any disconnected graph is connected.
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 vwu is a path in G'.

$\begingroup$ (Note that this implies the same result for unlabeled graphs, though enumeration is harder.) $\endgroup$ Nov 4 '10 at 23:04

1$\begingroup$ Obvious comment: to get strict inequality we should exhibit connected graphs whose complement is also connected. Let $P_n$ be the path on $n$ vertices. Note that if $n \geq 7$, then any two vertices of $P_n$ have a common nonneighbour, so the complement is connected with diameter 2. It is easy to check by hand that the complements of $P_4, P_5$ and $P_6$ are all connected. Finally for $n=2,3$ there are no graphs whose complement is connected. $\endgroup$ Nov 5 '10 at 1:36

3$\begingroup$ Actually, I like it better without the proof. :) $\endgroup$ Nov 5 '10 at 13:07

$\begingroup$ Tony: Alternatively, take any tree T. The only way T' can be disconnected is if the n1 missing edges are all incident to the same vertex, i.e. if T was the star graph. So for any other tree, both T and T' are connected. $\endgroup$ Nov 5 '10 at 14:51

2$\begingroup$ This argument is simple and amazingdoes anyone know the original reference? $\endgroup$ Nov 6 '10 at 7:55
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.)

2$\begingroup$ Awesome. I was going to follow up with whether most graphs are kconnected (when n is sufficiently large), and this sounds like a "yes". $\endgroup$ Nov 5 '10 at 1:39
Connectedness wins by a knockout: the proportion of disconnected graphs is about $n2^{n+1}$. See Flajolet, Sedgewick "Analytic Combinatorics", p. 138.

4$\begingroup$ (Note that this is also true for unlabeled graphs, since almost all large graphs have trivial automorphism groups.) $\endgroup$ Nov 4 '10 at 23:15
I like Jonah Ostroff's proof, but here is an inductive proof (for the heck of it).
Let $c(n)$ and $d(n)$ respectively denote the number of connected and disconnected graph on $n$ vertices.
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$.
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 nonempty 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.
Therefore,
\[ c(n+1) \geq (2^{n}1)c(n)+d(n) = (2^n2)c(n) + g(n). \]
By induction, we have $c(n) > g(n)/2$. Substituting yields
\[ c(n+1) > 2^{n1} g(n)=g(n+1)/2. \]
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:
the complement of each disconnected graph is a connected graph (which Ostroff points out)
the complement of a connected graph can also be a connected graph
thus the cardinality of the set of connected graphs must be larger than the cardinality of the disconnected graphs, because while there is a onetoone mapping of each disconnected graph onto a connected graph, there exist connected graphs which do not map to a disconnected graph
For example, for $n=4$:
Take the $12$ possible undrected Hamiltonian paths of length $4$ on a graph over four labeled vertices.
The complement of each of these paths is also a hamiltonian path.
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.
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,
yielding a total of $26$ disconnected graphs, and $26+12=38$ connected graphs over the set of $64$ labeled graphs over $4$ labeled vertices.
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$).

$\begingroup$ I meant undirected, not "unidirected" $\endgroup$ Nov 6 '10 at 4:59

1$\begingroup$ @TonyHuynh, I didn't notice that you also said essentially the same thing under Jonah Ostroff's answer, which is a halfanswer without the statement that complement(connected graph) can also be a connected graph, with path graphs of $n$ vertices as the exemplar. I like your inductive approach in your own answer better. $\endgroup$ Nov 6 '10 at 10:30

$\begingroup$ As I mention in a comment to my answer, you can generalize these paths a bit to any tree, so long as that tree isn't a star graph. The nice thing about that generalization is you don't have to check any cases by hand. $\endgroup$ Nov 6 '10 at 15:44