In this short post, we are only dealing with simple graphs where is a non-empty set and .
When talking about connected graph, one usually has the following definition in mind:
Definition 1. A graph is said to be connected if for any distinct vertices there is a path connecting and . (A path from to is an injective map for some positive integer , such that for all .)
Note the similarity to path connectedness in topology.
Definition 2. A graph is said to be connected if for any subset of with there is such that .
Again, there is a topological equivalent: we say that a topological space is connected if no subset of with is both open and closed (“clopen”).
But the analogy of the connectedness in topological spaces and in graphs only goes so far. Recall that every path-connected topological space is connected, but not vice versa. However, and possibly a bit surprisingly even for infinite graphs, we have:
Lemma. The definitions 1 and 2 above agree.
Proof. It is quite straightforward to show that path-connectedness as in definition 1 implies connectedness as in definition 2. Suppose that is connected in the sense of definition 2 but not 1. Pick any and let . ( is the pathwise connected component of .) It is easy to see that is a proper subset of because of our assumption. However, since is connected in the 2nd sense, there is an edge connecting a point to some point . But since there is a path from to and also we can extend the path so that it leads from to . So , contradicting .