Two definitions of connectedness in graphs

In this short post, we are only dealing with simple graphs G = (V,E) where V is a non-empty set and E \subseteq {\cal P}_2(V) := \{\{a,b\} \subseteq V: a \neq b\}.

When talking about connected graph, one usually has the following definition in mind:

Definition 1. A graph G=(V,E) is said to be connected if for any distinct vertices a,b \in V there is a path connecting a and b. (A  path from a to b is an injective map p: \{0,...n\} \to V for some positive integer n, such that \{p(k), p(k+1)\} \in E for all 0 \leq k < n.)

Note the similarity to path connectedness in topology.

Definition 2. A graph G=(V,E) is said to be connected if for any subset S of V with \emptyset \neq S \neq V there is e \in E such that S \cap e \neq \emptyset \neq (V\setminus S) \cap e.

Again, there is a topological equivalent: we say that a topological space (X,\tau) is connected if no subset S of X with \emptyset \neq S \neq X 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 G = (V,E) is connected in the sense of definition 2 but not 1. Pick any x \in V and let C = \{x\} \cup \{ v\in V: \textrm{ there is a path from } x \textrm{ to } v\}. (C is the pathwise connected component of x.) It is easy to see that C is a proper subset of V because of our assumption. However, since G is connected in the 2nd sense, there is an edge connecting a point c \in C to some point y \in V\setminus C. But since there is a path from x to c and also \{c, y\} \in E we can extend the path so that it leads from x to y. So y \in C, contradicting y \in V\setminus C.


About dominiczypen

I'm interested in general topology, order theory, and graph theory. This link takes you to my preprints on arXiv.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s