Prove that undirected graph G is connected if and only if it isn't a disjoint union of 2 graphs

115 Views Asked by At

I couldn't find such a proof in the web or in the forum. I managed to prove the -> direction, but am stuck on the <- direction.

1

There are 1 best solutions below

0
On BEST ANSWER

Instead of proving the reverse direction you can prove the negation of the forward direction:

if $G$ is not connected it is the disjoint union of two graphs.

This is trivial, since if $G$ is not connected it has more than one connected component, and the task reduces to splitting those connected components into two non-empty sets.

Together with the plain forward implication this is enough to conclude the given if-and-only-if relation.