Let $G$ be a graph with order $n ≥ 2$. Prove that $G$ satisfies $(a)$ if and only if it satisfies $(b)$.
$(a)$ for any pair of distinct vertices $u, v$ of $G$, there exists at least one $(u, v)$-path in $G$;
$(b)$ for any partition ${X, Y }$ of $V (G)$ into two non-empty parts $X, Y$ , there exists at least one edge $e = xy$ of $G$ such that $x ∈ X$ and $y ∈ Y$.
This is quite easy to understand intuitively but I'm having trouble trying to prove it, particularly proving $(b) \implies (a)$. Here's my approach to $(a) \implies (b)$:
Suppose $(a)$ is true, then $G$ is a connected graph. Let $X$ and $Y$ be $2$ non-empty partitions of $V(G)$. Suppose there is no such $e=xy$ of $G$ such that $x ∈ X$ and $y ∈ Y$. This means $G$ is disconnected which is a contradiction. So there exists at least one edge $e = xy$ of $G$ such that $x ∈ X$ and $y ∈ Y$.
I'm new to graph theory and proofs as such in general. I would really appreciate some feedback on the attempt above and some help with proving $(b) \implies (a)$. Thanks
You made use of the word "connected" all too quickly. We have to get hold of this notion first. Call two vertices $u$,$v\in V$ equivalent if there is an edge path in $G$ connecting $u$ and $v$.
Make sure that this is indeed an equivalence relation on the set $V$ of vertices of $G$. How many equivalence classes can there be if (b) holds?