Suppose we are talking about graphs with $n$ labeled vertices. Which graphs are more common: connected or disconnected?
$\begingroup$
$\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$– Leonid PetrovCommented 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$– Thierry ZellCommented Nov 4, 2010 at 22:26
-
4$\begingroup$ You mean connected clearly wins out, Thierry? For 4 vertices, 38/64 are connected. $\endgroup$– Jonah OstroffCommented Nov 4, 2010 at 22:55
-
$\begingroup$ This is basically a duplicate of this question: mathoverflow.net/questions/13088/… $\endgroup$– Matthew KahleCommented Nov 6, 2010 at 22:55
Add a comment
|
5 Answers
$\begingroup$
$\endgroup$
6
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'.
answered Nov 4, 2010 at 22:53
-
1$\begingroup$ (Note that this implies the same result for unlabeled graphs, though enumeration is harder.) $\endgroup$ Commented 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$ Commented Nov 5, 2010 at 1:36
-
3$\begingroup$ Actually, I like it better without the proof. :) $\endgroup$ Commented 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$ Commented Nov 5, 2010 at 14:51
-
2$\begingroup$ This argument is simple and amazing--does anyone know the original reference? $\endgroup$ Commented Nov 6, 2010 at 7:55
$\begingroup$
$\endgroup$
1
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.)
answered Nov 5, 2010 at 1:28
-
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$ Commented Nov 5, 2010 at 1:39
$\begingroup$
$\endgroup$
1
Connectedness wins by a knockout: the proportion of disconnected graphs is about $n2^{-n+1}$. See Flajolet, Sedgewick "Analytic Combinatorics", p. 138.
-
6$\begingroup$ (Note that this is also true for unlabeled graphs, since almost all large graphs have trivial automorphism groups.) $\endgroup$ Commented Nov 4, 2010 at 23:15
$\begingroup$
$\endgroup$
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. \]
answered Nov 4, 2010 at 22:27
$\begingroup$
$\endgroup$
3
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$).
answered Nov 6, 2010 at 4:57
-
$\begingroup$ I meant un-directed, not "uni-directed" $\endgroup$ Commented 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$ Commented 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$ Commented Nov 6, 2010 at 15:44