4 deleted 78 characters in body

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) \geq > 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) \geq > g(n)/2$. Substituting yields

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

Remark. It is easy to adapt the proof to get strict inequality.

3 added 1 characters in body

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) \geq 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) \geq g(n)/2$. Substituting yields

$c(n+1) \geq 2^{n-1} g(n)=g(n+1)/2.$

Remark. It is easy to adapt the proof to get strict inequality.

Post Undeleted by Tony Huynh
2 added 614 characters in body; deleted 3 characters in body
Post Deleted by Tony Huynh
1