Prove that a graph is connected if and only if for every partition of its vertices into two nonempty sets Prove that a graph is connected if and only if for every partition of its vertices into two nonempty sets, there is an edge with endpoints in both sets.
My proof:
Let $V=V(H)$ where $H$ is not connected. Let there be a component $A$ such that $C=V(A)$ and $M$ contains the vertices not in $C$.  $C$ and $M$ will then partition $V$ into nonempty sets.  Then by the definition of component, there is not an edge from $C$ to $M$. This is a contradiction! 
I am unsure how to prove the converse to make the if and only if statement true.
 A: You’ve shown that if for each partition of the vertices of $G$ into two non-empty sets there is an edge with endpoints in both sets, then $G$ is connected. For the converse, suppose that there is a partition $\{V_0,V_1\}$ of the vertices of $G$ into two non-empty sets such that there is no edge with endpoints in both $V_0$ and $V_1$; you want to show that $G$ is not connected.


*

*Show that $G$ is the union of the subgraphs induced by $V_0$ and $V_1$, and conclude that $G$ is not connected. In fact, each of these subgraphs is a union of components of $G$.

A: I found another proof for the converse of this theorem  
First of all assume that the given Graph $G$ is connected i.e., for any vertex pair
$(u,v)$ there exists a path of the form $P = u,x_1,x_2,x_3,x_4,\ldots,x_{n-1},v.$  
Now, let us assume that the vertex set of $G$ is divided into two partitions $X$ and $Y$ such that $(X \cup Y)=V(G)$,  also, let $u$ belongs $X$ and $v$ belongs $Y$.  
There are two possibilities
1)  Either $v$ is the only vertex present in this path which belongs to the set $Y$
2)  There are more than one vertex $x_i$, (index $i$) such that $x_i$ belongs to $Y$  
In the first case we can easily see that the vertex just preceding $v$ will obviously belong to the subset $X$ as $v$ has been assumed to be the only one belonging to the set $Y$ . Thus we get an edge of the form $(x_{n-1},v)$ where one vertex belongs to $X$ and the other belongs to $Y$.  
In the second case we can look for the smallest indexed vertex $x_i$, among the set of vertices belonging to $Y$ in the path $P$. Now ,obviously the vertex just before this $x_i$ belongs to $X$ and not $Y$. Hence, again we get an edge of the form $(x_{i-1},x_i)$ such that the one end point of the edge lies in the set $X$ and the other lies in the set $Y$.
Hence proved.
For the source go to this link 
