Graph theory -decomposition into connected components Can anyone give me ideas on how to prove the following:
"Every graph can be decomposed into connected components."
I have been looking at many different things but they all seem to delve much deeper than I think this question requires and become too specific, for example strongly connected graphs.
I appreciate any ideas you have!
 A: If you look at the Algorithms section of the Wikipedia page on connected components, you will find a description of an algorithm to find all connected components of a graph. More precisely:

"To find all the connected components of a graph, loop through its vertices, starting a new breadth first or depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component."

The same Wikipedia page also describes an equivalence relation called reachability, and states that "the connected components [of a graph] are then the induced subgraphs formed by the equivalence classes of this relation".
It is not difficult to see that this is true. If we fix an equivalence class, any two vertices in the induced subgraph are connected through a path, by definition of reachability. So certainly this subgraph is connected. Now, if this subgraph did not correspond to a connected component, this would mean that there is a pair of vertices, connected through a path, but that do not lie in the same equivalence class (or a pair of vertices in the same equivalence class, but not connected through a path) -- which is clearly inconsistent with the definition of reachability. Therefore, vertices lying in the same connected component must be in the same equivalence class. 
To sum up, equivalence classes clearly correspond to vertex sets of connected components, and the definition of induced subgraph means that the edge sets also match.
