MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

2 oops : fixed arithmetic error and typo

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 unidrected 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 = 56$ 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$). 1 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 unidrected Hamiltonian paths 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 = 56$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.