Numbers of ways $k - 1$ edges to be added to $k$ connected components to make the graph connected Given a graph $G$ with $n$ vertices and $m$ edges. Let us say it has $k$ connected components. Find out how many numbers of ways you can add $k - 1$ edges to make the graph connected.  
Is it any standard graph problem? How can it be solved?
 A: Notice that if you consider the $k$ components as vertices, then if you add the $k-1$ edges to make the graph connected you actually get a tree of $k$ vertices. So every tree on $k$ vertices generates a set of ways to connect the graph. One can see(prove) that different trees generate disjoints sets of ways of connecting the graph.
Label the components by $1, 2 \cdots,k$ and their sizes by $a_1, a_2, \cdots, a_k$. If $T$ is on the set of vertices $\{1, 2 \cdots,k \}$, then the number of ways of connecting an edges $(i, j) \in E(T)$ is $n_{i,j} = a_ia_j$ 
Thus, the number of ways of connecting the components using $T$ is $\prod_{(i,j) \in E(T)}n_{i,j} = \prod_{i=1}^ka_i^{d_i}$ where $d_i$ is the degree of vertex $i$ in the tree $T$.
So, the number of ways of connecting the components is   
$\sum_{T \text{ tree of } K_k}\prod_{i=1}^ka_i^{d_i} = \sum_{\sum_{i=1}^nd_i = 2(k-1)}N(d_1, d_2, \cdots, d_k)\prod_{i=1}^ka_i^{d_i}$ where $N(d_1, d_2, \cdots, d_k)$ is the number of labeled trees on $k$ vertices and labeled vertex $i$ has degree $d_i$. 
We have $N(d_1, d_2, \cdots, d_k) = \dfrac{(k-2)!}{\prod\limits_{i=1}^{k}(d_i-1)!}$ see here for more info.
So, $\sum_{T \text{ tree of } K_k}\prod_{i=1}^{k}a_i^{d_i}  = \sum_{\sum_{i=1}^nd_i = 2(k-1)} (k-2)! \prod_{i=1}^k \frac {a_i^{d_i}}{(d_i - 1)!}$
$= (\prod_{i=1}^k a_i)\sum_{\sum_{i=1}^n(d_i-1) = k-2} (k-2)! \prod_{i=1}^k \frac{a_i^{d_i-1}}{(d_i - 1)!}$
$= (\prod_{i=1}^k a_i)(\sum_{i=1}^{k} a_i)^{k-2}$ (by multinomial expansion theorem.)
Therefore the number you are seeking is $(\prod_{i=1}^k a_i)(\sum_{i=1}^{k} a_i)^{k-2}= n^{k-2}(\prod_{i=1}^k a_i)$ since $\sum_{i=1}^{k} a_i = n$ the total number of vertices.
A: The number of vertices, edges, and connected components of a graph do not completely determine the number of ways to add $k-1$ edges to connect the graph. For example, let $n=5, m=3, k=2$. Consider two cases: $G_1=(V,E_1)$ and $G_2=(V,E_2)$ where $V=\{1,2,3,4,5\}$ and
$$
E_1=\{(1,2),(2,3),(3,4)\}\\
E_2=\{(1,2),(3,4),(4,5)\}
$$

                           

It's not hard to see that the number of ways to add $1$ edge to $G_1$ to make it connected equals $4$ whereas the number of ways to add $1$ edge to $G_2$ to make it connected equals $6$.
A: You can do this using induction and the Principle of inclusion and exclusion.
The sizes $a_i$ of the components $c_i$ must be known to calculate the answer (see the post by Kuai). When $k=1$, the answer is $1$ (the only way of making it connected is by doing nothing). When $k=2$, the answer is $a_1=1a_2$. Let $$F_i(a_1,a_2,\dots a_i)$$
be the number of ways to connect $i$ components with sizes $a_1$ to $a_i$. We know $F_1(a_1)=1$ and $F_2(a_1,a_2)=a_1a_2$. We are going to calculate $F_k(a_1,\dots ,a_k)$.
Now, we take the first component. We know it has to be connected to at least one of the other components. We can calculate the number of possibilities when $c_1$ is connected with $c_i$ ($i\neq 1$):
$$
a_1a_iF_{k-1}(a_1+a_i,a_2,\dots,a_{i-1},a_{i+1},\dots ,a_k)
$$
We can sum over all $2\leq i\leq k$, but then, we will count some connections two or more times, because sometimes $c_1$ is direcly connected to more than one other component. The number of times when $c_1$ is connected to $c_i$ and $c_j$ ($2\leq i<j\leq k$) is
$$
(a_1a_i)(a_1a_j)F_{i-2}(a_1+a_i+a_j,a_2,\dots,a_{i-1},a_{i+1},\dots ,a_{j-1},a_{j+1},\dots ,a_k)
$$
Now define $F(I)$ for subsets of $\{2,3,\dots,k\}$:
$$
F(I)=F_{k-|I|}\left(a_1+\sum_{i\in I} a_i,\underbrace{a_2,a_3,\dots,a_k}_{\text{all $a_i$ with } i\not\in I}\right)
$$
By the principle of inclusion and exclusion, we now find that (prepare yourself):
$$
F_k(a_1,\dots,a_k)=\sum_{i=2}^ka_1a_iF_{k-1}(a_1+a_i,a_2,\dots,a_k)\\-\sum_{2\leq i<j\leq k}a_1^2a_ia_jF_{k-2}(a_1+a_i+a_j,a_2,\dots,a_{i-1},a_{i+1},\dots ,a_{j-1},a_{j+1},\dots ,a_k)+\dots\\
=\sum_{I\subseteq N}(-1)^{|I|-1}a_1^{|I|}\prod_{i\in I}a_i\cdot F(I)
$$
where $N=\{2,3,\dots,n\}$.
This can be evaluated for any $k$, and by induction we can find $F_k$ for any $k$. I'll edit this post when I have found an (almost) closed form for it.
