Denote by $g_n$ the number of connected graphs of degree $n$ whose vertices are labeled with numbers $1,2,...,n$. Prove that $g_n \ge (\frac{1}{2}).2^{\frac{n(n-1)}{2}}$. Note:If you prove that for $c < \frac{1}{2}$, $g_n \ge c.2^{\frac{n(n-1)}{2}}$, you will earn some point! proposed by Seyed Reza Hosseini and Mohammad Amin Ghiasi
Problem
Source: Iranian 3rd round Combinatorics exam P1 - 2014
Tags: combinatorics proposed, combinatorics