The question below is from First Course in Graph Theory book:
For a graph G, a component of G has been defined as:
- a connected subgraph of G that is not a proper subgraph of any other connected subgraph of G
- a subgraph of G induced by the vertices in an equivalence class resulting from the equivalence relation defined in the following theorem: Let R be the relation defined on the vertex set of a graph G by u R v, where u, v ∈ V(G), if u is connected to v, that is, if G contains a u − v path. Then R is an equivalence relation.
The question asks to prove that both the statements are equivalent. Am I just proving that equivalence classes means its a connected graph and vice versa. A bit confused. And by the equivalence class, is it just showing that its reflective, transitive, symmetric. Any hints would help!
I don’t think showing the equivalence relation is supposed to be part of the exercise, so let me briefly explain it.
Consider the definition of the relation. It tells us that two vertices are equivalent if and only if there is a path between them. This is obviously a reflexive and transitive relation (one can concatenate paths) and as long as you consider undirected graphs it is a symmetric relation as well. In other words its an equivalence relation. Instead of $u\sim v$ we might as well say $u$ is connected to $v$. Then the equivalence class of some vertex $x$ just becomes the set of all vertices connected to $x$.
Now towards the exercise. You are supposed to show that given a vertex $x$, the maximal connected subgraph containing $x$ coincides with the full subgraph on all the vertices connected (in the sense of our equivalence relation above) to $x$.