5
$\begingroup$

Does an infinite connected graph mean that given any two vertices there is a path of finite length joining them or the path may be of infinite length?

$\endgroup$
  • 1
    $\begingroup$ This is a good question, and I'm surprised to find that it doesn't seem to be addressed in most graph theory texts (or maybe I overlooked it). Do you have a specific graph in mind for which this subtle (but fundamental) difference determines whether or not it is connected? Mind you, my experience with infinite graphs is limited, but no such graph springs to mind. For instance, there doesn't seem to be a meaningful way to interpret the infinite cyclic group $\mathbb{Z}$ as an infinite cycle, in such a way that we can remove one vertex and still have a connected graph. $\endgroup$ – Josse van Dobben de Bruyn Apr 2 '16 at 23:40
  • $\begingroup$ Some good points are made in the answers to this question. Your question is close to being a duplicate, although you ask a fundamentally different question. It is my opinion that this is not a duplicate, but other members of this community might disagree. In any case, the answers to the other question qualify as recommended reading. :-) $\endgroup$ – Josse van Dobben de Bruyn Apr 3 '16 at 1:11
  • 2
    $\begingroup$ What would be an example of a graph with a "path of infinite length" joining two vertices? $\endgroup$ – Eric Wofsey Apr 3 '16 at 1:42
  • $\begingroup$ @EricWofsey: note that by now this concern has been appropriately addressed, both in the answers below and in the answers to the other question. :-) $\endgroup$ – Josse van Dobben de Bruyn Apr 3 '16 at 1:49
  • 2
    $\begingroup$ I was asking OP what they meant by the phrase, since it's very nonobvious what it should mean. $\endgroup$ – Eric Wofsey Apr 3 '16 at 1:50
6
$\begingroup$

Diestel's Graph Theory deals with infinite graphs in chapter 8. He also considers certain infinite paths, namely the ray (indexed by $\mathbb{N}$) and the double ray (indexed by $\mathbb{Z}$). A path in an infinite graph may be either a finite path, a ray or a double ray. However, out of these options the finite path is the only one with two endpoints. Thus, when dealing with connectivity, indeed it is required that any pair of vertices can be joined by a finite path.

You can also approach the definition of connected components from another perspective. Let us say that a connected component in a graph $G = (V,E)$ is an inclusionwise minimal non-empty vertex set $C \subseteq V$ such that every edge $e\in E$ having one endpoint in $C$ does in fact have both endpoints in $C$. (In other words, a minimal non-empty vertex set that has no edges going in/going out.) Let $C$ be a component and let $a\in C$ be fixed. Now let $F_a \subseteq V$ be the set of vertices that can be reached from $a$ through a path of finite length. Now:

  • We can prove by induction that $F_a \subseteq C$ must hold: we have $a \in C$, so every neighbour of $a$ must also belong to $C$, and every neighbour of every neighbour of $a$ must then also belong to $C$, and so on.
  • On the other hand, one easily shows that $F_a$ satisfies the property described above, namely that every edge having one endpoint in $F_a$ also has the other endpoint in $F_a$. Thus, by minimality of $C$, we cannot have $F_a \subsetneq C$, so we find that $F_a = C$ must hold.

Thus, indeed we see that vertices belonging to the same component can be joined by a finite path. (We have to be a bit careful with this approach: it is not a priori clear from the definition that connected components should exist at all, or that two connected components $C_1,C_2\subseteq V$ are either equal or disjoint. Luckily, one easily shows that $F_a$ is indeed a connected component for every fixed $a\in V$, and the remaining properties can be deduced after that.)

Various standard examples of infinite graphs are connected in this sense: the ray $\mathbb{N}$, the double ray $\mathbb{Z}$, the (countably) infinite complete binary tree, but also the unit distance graph of the plane, where the vertex set is $\mathbb{R}^2$, and two vertices are connected if and only if the Euclidean distance between them is exactly $1$. (Fun exercise: find a formula for the length of the shortest path between two points in the unit distance graph.)


Off topic: It is quite interesting to consider a more abstract type of path, which is indexed by other kinds of sets. For instance, user GregRos gives a list of requirements for the index set $I$: it must be a bounded linearly ordered set, and every element must have a unique successor (except for the greatest element) and predecessor (except for the least element). Let us call the connected components for this generalised notion of paths the generalised components.

I'm a little confused by the example he provides, since I am unfamiliar with the hypperreals, but it seems that one fundamental requirement is still missing: $I$ should itself be connected in some sense. For instance, consider the following example:

Example. Consider the index set $I = \mathbb{Z}$ with the linear order $\prec$ defined in the following way: $$ 0 \prec 1 \prec 2 \prec 3 \prec \cdots \prec -4 \prec -3 \prec -2 \prec -1. $$ That is, the subsets $\mathbb{Z}_{\geq 0}$ and $\mathbb{Z}_{<0}$ are ordered in the usual way, but we declare that every negative number is larger than every non-negative number. The order is indeed linear and bounded: the greatest element is $-1$ and the least element is $0$. Furthermore, every element has a unique successor (except for the greatest element) and a unique predecessor (except for the least element). Thus, this ordered set meets all the requirements. Note that there is no edge going from $\mathbb{Z}_{\geq 0}$ to $\mathbb{Z}_{<0}$. Therefore any pair of rays in an infinite graph can be joined by a path indexed by $(\mathbb{Z},\prec)$.

The path from the example above is essentially the only new type of path that we gain from this generalisation:

Proposition. Let $P$ be an infinite path indexed by an index set $I$ that meets GregRos's requirements. Then $P$ contains a subpath indexed by the ordered set $(\mathbb{Z},\prec)$ from the example above.

Proof. Let $a$ and $b$ be the endpoints of $P$ and let $s : P \setminus\{b\} \to P$ and $p : P \setminus\{a\} \to P$ denote the successor and predecessor functions on $P$. Define $x_0,x_1,x_2,\ldots$ recursively by setting $$ x_n = \begin{cases} a,&\quad\text{if $n = 0$};\\[1ex] s(x_{n-1}),&\quad\text{if $n > 0$}. \end{cases} $$ This is well defined since the path $P$ is assumed to be infinite (at every step we have $x_n \neq b$, so that $x_n$ has a successor). Similarly, we define $x_{-1},x_{-2},x_{-3},\ldots$ recursively by setting $$ x_n = \begin{cases} b,&\quad\text{if $n = -1$};\\[1ex] p(x_{n+1}),&\quad\text{if $n < -1$}. \end{cases} $$ We see that $\{x_n\}_{n\in\mathbb{Z}}$ is a path indexed by $(\mathbb{Z},\prec)$.$\hspace{2mm}\blacksquare$

Thus, if we have two vertices $a$ and $b$ that can be joined by an infinite path, they can also be joined by a path indexed by $(\mathbb{Z},\prec)$. Now it is easy to determine the connected components according to this wider definition of paths:

Proposition. Two vertices $a$ and $b$ lie in the same generalised component if and only if at least one of the following criteria is met:

  • There is a finite path joining $a$ and $b$.
  • Both $a$ and $b$ lie on a ray.

Note: for every original component we have that either every vertex or no vertex of the component lies on a ray. Thus, when we consider this generalisation of the concept of paths, we essentially obtain a sort of one-point compactification of our original graph: we have the same components as before, except that the components containing a ray are joined at infinity. (Note however that the disjoint union of the countably infinite star graph $S_{\omega}$ and a ray is still disconnected, for only one of the components contains a ray. In particular, there might be more than one generalised component with infinitely many vertices. So perhaps my comparison with one-point compactifications is a little confusing: one might argue that the countably infinite star graph $S_{\omega}$ is not locally compact to begin with.)

This is all very interesting, but in the literature it is assumed that vertices in the same component are joined by a finite path.

$\endgroup$
  • $\begingroup$ The same issue comes up when using hyper-integers (except worse, since you can find an infinite number of such pairs). Another interesting observation, in your example, is that the sets $ℤ_{≥0}$ and $ℤ_{<0}$ aren't paths between any two vertices, but their union $ℤ$ is the path between $0$ and $-1$. But still, every vertex is connected to every other vertex, and in a very intuitive sense, every "step" along the path brings you "closer" to the end (I could elaborate, but I'd run afoul of the character limit). Just because it's strange doesn't mean it's meaningless. $\endgroup$ – GregRos Apr 5 '16 at 13:17
  • $\begingroup$ You can call different kinds of paths "half-open", and "closed' paths, and note that a closed path may have half-open subpaths and the other way around. A closed path might have half-open subpaths if and only if it is an infinite path (in the set-theoretic sense). Or maybe it doesn't. Maybe there are graphs where this doesn't hold. There are lots of questions you can ask. $\endgroup$ – GregRos Apr 5 '16 at 13:22
  • $\begingroup$ You're right; it's actually quite interesting to consider these kinds of possibilities. :-) I elaborated on the generalised components in my answer above: they don't differ too much from the original connected components where vertices must be joined by finite paths. Let me ask you this: are you just being creative, or did you read about these kinds of infinite paths somewhere in literature? :-) $\endgroup$ – Josse van Dobben de Bruyn Apr 5 '16 at 22:46
3
$\begingroup$

An infinite graph is connected iff for any vertices $u, v$, there is a finite path $x_0 x_1 x_2 \dots x_n$ with $u = x_0, v = x_n$ and no $x_i$ duplicated.

$\endgroup$
  • $\begingroup$ Why does the path length have to be finite? $\endgroup$ – Banach Tarski Apr 1 '16 at 17:48
  • $\begingroup$ I have the same query as above. $\endgroup$ – Angsuman Apr 1 '16 at 18:10
  • 1
    $\begingroup$ @BanachTarski By definition. We all know what the path $P_n$ on $n$ vertices looks like; what might $P_{\infty}$ look like anyway? There's several different options, so we just say that a "path" is finite unless otherwise specified. $\endgroup$ – Patrick Stevens Apr 1 '16 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.