12
$\begingroup$

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

$\endgroup$
4
  • $\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 sub-question is of much less interest for me now. $\endgroup$ Nov 4, 2010 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$ Nov 4, 2010 at 22:26
  • 4
    $\begingroup$ You mean connected clearly wins out, Thierry? For 4 vertices, 38/64 are connected. $\endgroup$ Nov 4, 2010 at 22:55
  • $\begingroup$ This is basically a duplicate of this question: mathoverflow.net/questions/13088/… $\endgroup$ Nov 6, 2010 at 22:55

5 Answers 5

63
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ (Note that this implies the same result for unlabeled graphs, though enumeration is harder.) $\endgroup$ Nov 4, 2010 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 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. $\endgroup$
    – Tony Huynh
    Nov 5, 2010 at 1:36
  • 3
    $\begingroup$ Actually, I like it better without the proof. :) $\endgroup$ Nov 5, 2010 at 13:07
  • $\begingroup$ 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. $\endgroup$ Nov 5, 2010 at 14:51
  • 2
    $\begingroup$ This argument is simple and amazing--does anyone know the original reference? $\endgroup$ Nov 6, 2010 at 7:55
27
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ 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". $\endgroup$ Nov 5, 2010 at 1:39
24
$\begingroup$

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

$\endgroup$
1
  • 5
    $\begingroup$ (Note that this is also true for unlabeled graphs, since almost all large graphs have trivial automorphism groups.) $\endgroup$
    – zhoraster
    Nov 4, 2010 at 23:15
11
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ I meant un-directed, not "uni-directed" $\endgroup$ Nov 6, 2010 at 4:59
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 6, 2010 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, 2010 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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