1
$\begingroup$

From Wikipedia:

"If there is no path connecting two vertices, i.e., if they belong to different connected components, then conventionally the distance is defined as infinite."

This seems to negate the possibility that there are graphs with vertices connected by an infinite shortest path (as opposed to being not connected).

Why is it that for every (even infinite) path between two vertices there is a finite one?

Note that infinite paths between vertices do exist - e.g. in the infinite complete graph -, but they are not the shortest.

$\endgroup$
  • 7
    $\begingroup$ I don't understand what you mean by an infinite path between vertices. $\endgroup$ – Qiaochu Yuan May 16 '11 at 7:22
  • 2
    $\begingroup$ @Hans: You can have an infinite path in an infinite graph in the sense that you can have an infinite sequence of edges such that consecutive edges share a vertex, but that's not an infinite path connecting two vertices. Any two vertices connected by this "path" are connected by a particular finite section of it. $\endgroup$ – joriki May 16 '11 at 7:35
  • 5
    $\begingroup$ The issue I have with this question is that no definitions are given and we're only talking about musings. Either we're speaking of graphs and paths, then the question is no one, because it has the obvious answer that needs not be discussed, or we don't and the question needs to be reformulated by providing precise definitions or asking about them. As it is, it's just not a real question, I'm sorry. $\endgroup$ – t.b. May 16 '11 at 7:49
  • 2
    $\begingroup$ @Hans: a Hamiltonian path in the infinite complete graph (if I understand your meaning) either has zero or one endpoints. If it has two endpoints, then it is finite. $\endgroup$ – Qiaochu Yuan May 16 '11 at 7:53
  • 3
    $\begingroup$ @Hans: On an "infinite path connecting two vertices", you could start at either vertex and walk infinitely long without ever reaching the other vertex. How would this differ from two separate infinite paths starting at the two vertices? What would it mean to say that the path nevertheless "connects" the two vertices? $\endgroup$ – joriki May 16 '11 at 8:06
8
$\begingroup$

To expand on my comment: It's clear that if an infinite path is defined as a map from $\mathbb N$ to the edge set such that consecutive edges share a vertex, then any vertices connected by such an infinite path are in fact connected by a finite section of the path. To make sense of the question nevertheless, one might ask whether it is possible to use a different ordinal than $\omega$, say, $\omega\cdot2$, to define an infinite path. But that doesn't make sense either, since there's no way (at least I don't see one) to make the two parts of such a path have anything to do with each other -- at each limit ordinal, the path can start wherever it wants, since there's no predecessor for applying the condition that consecutive edges share a vertex.

Note that the situation is different in infinite trees, which can perfectly well contain infinite paths connecting the root to a node. This is because the definition of a path in an infinite tree is different; it explicitly attaches the nodes on levels corresponding to limit ordinals to entire sequences of nodes, not to individual nodes; such a concept doesn't exist in graphs.

$\endgroup$
  • 3
    $\begingroup$ To add a bit on the trouble there, if you want to inverse the path you will get a descending sequence of ordinals, therefore it will have to be finite. $\endgroup$ – Asaf Karagila May 16 '11 at 8:17
5
$\begingroup$

The point I made in the comments is that standard graph-theoretic terminology does not allow you to make sense of the notion of two points being connected by an infinite path. However, for what it's worth, there is a formalism that allows you to make sense of this related to end compactification: see Diestel's survey Locally finite graphs with ends: a topological approach for details. Briefly, we have to add extra vertices "at infinity," then introduce a nontrivial topology, after which we can speak of two vertices connected by a continuous function from $[0, 1]$ that passes through infinitely many vertices.

In any case, the excerpt from the Wikipedia article is about the standard graph-theoretic context. In the standard graph-theoretic context, we sometimes want to think of a graph as an extended metric space, and a natural way to do that is to define the distance to be infinite if two vertices aren't connected by an edge; certainly there's no sensible finite value, and if you choose infinity then the triangle inequality holds.

A very general context in which to understand this assignment is to think of the distance $d(u, v)$ between two vertices as the infimum over the lengths of all paths between $u$ and $v$. If $u, v$ are not connected by a path, this infimum is empty, and the empty infimum in a poset is always the greatest element, if it exists. This is a special case of a general fact in category theory that the empty limit is the terminal object. (Here the category is the poset $0 < 1 < 2 < ... < \infty$, regarded as a category where there is a single arrow $a \to b$ if $a \le b$ and no arrows otherwise.)

$\endgroup$
  • $\begingroup$ Thank you very much for your clarifications! $\endgroup$ – Hans-Peter Stricker May 16 '11 at 9:12
3
$\begingroup$

Traditional graph theory focuses on finite graphs. Two vertices are considered connected iff there is a finite walk between them (basically a sequence of vertices, each one adjacent to the last).

If we start considering infinite graphs, we have to consider some interesting consequences. Suppose we want to consider vertices x,y as connected by an infinite walk. Then we can order this walk linearly, and get a sequence $x=x_1,x_2,x_3,\ldots,x_\infty=y$. If this is an infinite sequence, it must contain some limit point -- some point $x_k$ must have either no immediate predecessor or no immediate successor. This idea doesn't match the old definition of a walk between vertices.

Although I don't know of any references, I do think this idea is interesting as a way to extend connected concepts to infinite graphs.

For example, consider the tree of surreal numbers. Think of the surreals as sign sequences; each is a map from an ordinal to $\{-,+\}$. Say that $s$ and $t$ are adjacent if the domain of $s$ is one more or one less than the domain of $t$. So 0 is adjacent to -1 and 1, 1 is adjacent to 0, 2, and 1/2, etc.

This looks like a standard tree until we get surreals with infinite domains. Consider some $s$ with domain $\omega$, and the sequence $s_i$ where $s_i$ has domain $i = \{j:j<i\}$, and $s_i(j)=s(j)$. It feels like the $s_i$ walk should connect 0 with $s$. A new definition to capture this idea would be interesting.

$\endgroup$
  • $\begingroup$ Oh, I guess @joriki has seen this idea elsewhere already. Any references? $\endgroup$ – Tyler May 16 '11 at 8:07
  • 1
    $\begingroup$ A tree can be defined as a partially ordered set with a unique minimal element such that for all elements $x$ the set of elements less than $x$ is totally ordered. This definition extends to infinite trees. You can read a bit about such infinite trees here, for instance: maa.org/devlin/devlin_01_06.html $\endgroup$ – joriki May 16 '11 at 8:18

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.