What is the maximum number of vertices in a connected graph $G$ if we are given that every vertex has degree $\binom{n}{2}$?
For small cases (1,2,3,4), the answer seems to be $2^{n-1},$ but how would you go about proving this? Is there a way to find an isomorphism between subsets of edges from a vertex and vertices?
As long as $n \ge 3$, so ${n \choose 2} \ge 3$, there is no maximum. Start with a cycle graph $C_N$ on vertices $1 \ldots N$ where $N$ is a large integer. This is already connected, and each vertex has degree $2$. Adding more edges will keep it connected. To add $2k$ more edges to every vertex, join each vertex to the vertices $2$ to $k+1$ positions ahead of it in the cycle (and thus also to those $2$ to $k+1$ positions behind. This works if $N \ge 2k+3$. If ${n \choose 2}$ is odd, you want to add one more edge per vertex. One way to do this is two take two copies of the current graph and join each vertex of one to its copy in the other.