Question on connected graphs Is it true that if for each partition of a graph G's vertices into two non empty sets there is an edge with end points in both sides then G is connected? Intuitively this seems true to me. But I cannot prove this. I would very much appreciate some assistance. Thanks 
 A: Yes, it is!
A graph is connected precisely when there is a path between any two vertices; however, another characterization is this:
Let $R$ be the relation on the vertex set $V$ defined by $vRw$ iff there is a path between $v$ and $w$.  It is not too hard to show that this is an equivalence relation, and so it partitions $V$ in to equivalence classes; a connected graph is a graph for which there is only one equivalence class.
This makes the result obvious: if you have multiple equivalence classes, pick one; the partition obtained by putting this equivalence class on one side and the rest on the other must have an edge crossing it.  But then the other end of that edge is in your equivalence class, a contradiction!
A: The statement is correct and one can show its contraposition as follows. Let $G(V,E)$ be a disconnected graph. Then by definition there exists a pair of vertices $i,j\in V$ such that there is no edge between them: $(i,j)\notin E$. Then we let $V_1$ and $V_2$ be a partition of $V$ such that $i\in V_1$ and $j\in V_2$ and we are done.
