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.
