Let G= (V; E) be a graph. Prove that G is a connected graph

Question

Let G = (V; E) be a graph. Prove that if for every partition of V into non-empty subsets, V1 and V2, there is an edge with one end in V1 and one end in V2 then G is a connected graph

Answer 1

One way to solve the problem is by proving the contrapositive: if $G$ is not a connected graph, then there exists a partition of $V$ into non-empty subsets $V_1$ and $V_2$ such that no edge has one edge in $V_1$ and one edge in $V_2$. Recall that the definition of a connected graph is one in which there is a path between every pair of vertices. Thus, we start by assuming that $G$ contains a pair of vertices not connected by a path, which makes $G$ not connected by definition.

Suppose there exist $s,t \in V$ such that no path exists between $s$ and $t$. Then, consider the connected component $C_s$ containing $s$ and the connected component $C_t$ containing $t$.

Hint 1: Show that $C_s \neq C_t$ and so in particular, there is no edge with one endpoint in $C_s$ and the other in $C_t$.

Hint 2: Denote a set of vertices $$V' = \{v \mid v \text{ is a vertex in any connected component other than $C_s$ or $C_t$}\}$$ Then consider the partition of vertices $$V_1 = \{v \mid v \text{ is a vertex in } C_s\} \cup V'$$ $$V_2 = \{v \mid v \text{ is a vertex in $C_t$}\}$$ Show that there cannot exist an edge with one end in $V_1$ and the other in $V_2$, thus completing the proof.