If $G$ is a graph, $G$ is not connected, then there are at least $2$ connected components of $G$.

1.1k Views Asked by At

If $G$ is a graph, $G$ is not connected, then there are at least $2$ connected components of $G$. I still cannot understand this statement. By definition of graph in my book, $G$ is a pair of $(V,E)$ where $V$ is vertices and $E$ is set of underordered pair of elements of $V$. If I set $V$ to be 3 vertices (1,2,3) and $E$ to be the edge connecting 1 and 2 but not the rest, then $G$ is not connected but there is only 1 connected component..? Sorry if it seems trivial cause my answer proof did not explain why.

1

There are 1 best solutions below

7
On BEST ANSWER

By the contrapositive, if $G$ has exactly one connected component, then any two points belong to this component, hence they are connected by some path. This is way the graph being connected means, by definition.

Here's a fun exercise that you can prove: the relation $v \sim w$ if there exists a path $\xi$ from $v$ to $w$ is an equivalence relation, and the partition it induces is exactly the one composed of connected components.