## 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$.

Advertisements

## 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.