Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 sub-question is of much less interest for me now. –  Leonid Petrov Nov 4 '10 at 21:17
1  
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... –  Thierry Zell Nov 4 '10 at 22:26
4  
You mean connected clearly wins out, Thierry? For 4 vertices, 38/64 are connected. –  Jonah Ostroff Nov 4 '10 at 22:55
    
This is basically a duplicate of this question: mathoverflow.net/questions/13088/… –  Matthew Kahle Nov 6 '10 at 22:55
add comment

5 Answers

up vote 46 down vote accepted

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 v-w-u is a path in G'.

share|improve this answer
    
(Note that this implies the same result for unlabeled graphs, though enumeration is harder.) –  Jonah Ostroff Nov 4 '10 at 23:04
1  
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 non-neighbour, 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. –  Tony Huynh Nov 5 '10 at 1:36
    
Actually, I like it better without the proof. :) –  Cam McLeman Nov 5 '10 at 13:07
    
Tony: Alternatively, take any tree T. The only way T' can be disconnected is if the n-1 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. –  Jonah Ostroff Nov 5 '10 at 14:51
1  
This argument is simple and amazing--does anyone know the original reference? –  Daniel Litt Nov 6 '10 at 7:55
show 1 more comment

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.)

share|improve this answer
1  
Awesome. I was going to follow up with whether most graphs are k-connected (when n is sufficiently large), and this sounds like a "yes". –  Jonah Ostroff Nov 5 '10 at 1:39
add comment

Connectedness wins by a knockout: the proportion of disconnected graphs is about $n2^{-n+1}$. See Flajolet, Sedgewick "Analytic Combinatorics", p. 138.

share|improve this answer
2  
(Note that this is also true for unlabeled graphs, since almost all large graphs have trivial automorphism groups.) –  zhoraster Nov 4 '10 at 23:15
add comment

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 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.

Therefore,

\[ c(n+1) \geq (2^{n}-1)c(n)+d(n) = (2^n-2)c(n) + g(n). \]

By induction, we have $c(n) > g(n)/2$. Substituting yields

\[ c(n+1) > 2^{n-1} g(n)=g(n+1)/2. \]

share|improve this answer
add comment

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 one-to-one 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 un-drected 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$).

share|improve this answer
    
I meant un-directed, not "uni-directed" –  sleepless in beantown Nov 6 '10 at 4:59
1  
@Tony-Huynh, I didn't notice that you also said essentially the same thing under Jonah Ostroff's answer, which is a half-answer 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. –  sleepless in beantown Nov 6 '10 at 10:30
    
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. –  Jonah Ostroff Nov 6 '10 at 15:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.