Necessary and Sufficient Conditions for Simplicity and Connectedness in Graphs A connected graph is a graph with no disjoint subgraphs. A simple graph is a graph with no loops or multiple edges. 
Easy Question: What are the necessary and sufficient conditions on the order (number of vertices) and size (number of edges) of a given graph in order to ensure that it is simple and connected?
For example, the only simple and connected graph of order $2$ and size $1$ is the path graph $P_2$ (a line segment). There is no simple and connected graph of order $2$ and size greater than or equal to $2$. A graph with order and size both $3$ is the cycle graph of order $3$ (a triangle). There is no simple and connected graph of order $3$ and size greater than or equal to $4$. Continuing in this fashion, I conclude that there must be a condition on the difference between the size and order (compared to the size).
Harder Question: For any pair of positive integers $(a,b)$ is there a simple and connected graph $G_{ab} = (V_{ab}, E_{ab})$ with order $|V_{ab}| = \frac{1}{2}(ab + a + b + \text{gcd}(a,b))$ and size $|E_{ab}| = ab$? If so, are such graphs significant?
For instance, if $b = 1$, then $|V_{ab}| = a + 1$, $|E_{ab}| = a$ and $G_{ab}$ can be realized as the path graph $P_{a+1}$ (or any tree with the same order), which is both simple and connected.
 A: Easy Question:
Suppose that $|V|=n$.  Then the graph cannot be simple if $|E|>\binom{n}{2}$ since the complete graph on $n$ vertices has $\binom{n}{2}$ edges.  The graph cannot be disconnected if it is simple and $|E|>\binom{n-1}{2}$.  This is because the complete graph on $n-1$ vertices has $\binom{n-1}{2}$ edges.  (See this MSE thread for a discussion and a proof.)  Note that for the connectedness requirement we must assume the graph is simple, otherwise we could just put all the edges between two vertices.
Harder Question: The answer is yes.  We will prove that this graph has more edges then the tree on $|V|$ vertices, and less edges then the complete graph on $|V|$ vertices.  (This means we can choose it to be simple and connected)
More than Tree:
Suppose $a\geq b$, and note that then $b\geq 1$, and if $b\neq 1$ we have $a\geq 2$.  Also, $\gcd(a,b)\leq b$ so that $$ |V|\leq \frac{1}{2}\left( ab+2b+a\right).$$  It then follows that  $$|E|-|V|\geq ab- \frac{1}{2}\left( ab+2b+a\right)$$
$$=\frac{1}{2}\left(ab-2b-a+2\right)-1=\frac{1}{2}(a-2)(b-1)-1\geq -1.$$  Consequently $$|E|-|V|\geq -1$$ so we have enough edges to connect the graph, as the connected tree on $|V|$ vertices has $|V|-1$ edges.
Less than Complete Graph:
We also do not have too many edges since $\gcd(a,b)\geq 1$ implies $$\frac{1}{2}\left( ab+b+a+1\right)\leq |V|.$$  This means $$|E|+b+a+1\leq2|V|,$$ and since $b\geq 1$, $a\geq1$ we have $|E|\leq 2|V|-3$.  But since $n^2-5n+6\geq 0$ for integers $n\geq 1$ we see that $\frac{n^2-n}{2}\geq 2n-3$ and hence $$2n-3\leq\binom{n}{2}$$ for every positive integer $n$.  Consequently, $|E|\leq 2|V|-3$ implies that $$|E|\leq \binom{|V|}{2}$$ so that the graph has less edges then the complete graph, and can be chosen to be simple.
Hope that helps,
