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.

  • 7
    I don't understand what you mean by an infinite path between vertices.2011-05-16
  • 0
    Doesn't a Hamiltonian path in the infinite complete graph qualify?2011-05-16
  • 0
    I also don't understand what an infinite path between vertices could be. However, in the comments to this answer: http://math.stackexchange.com/questions/34569/enigma-of-wizards-dwarves-and-hats/34577#34577, Aryabhatta also thought it might be possible to make sense of such a thing. Thus I vote against closing the question as not a real question (see http://meta.math.stackexchange.com/questions/1869/exercising-the-vote-not-to-close)2011-05-16
  • 2
    @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.2011-05-16
  • 0
    Why is thinking of a Hamiltonian path in the infinite complete graph connecting its two endpoints contradictory? Would this question deserve an answer?2011-05-16
  • 0
    @Joriki: Why is such a graph not connecting two vertices? My question is exactly for a proof of your final claim!2011-05-16
  • 1
    @Hans: Then I'm not sure I understand the question. Are you saying that an infinite path might connect two vertices without them being connected by some finite part of the path? If so, could you explain what that would mean? Also, perhaps my more elaborate answer below may shed some light on this?2011-05-16
  • 5
    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.2011-05-16
  • 2
    @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.2011-05-16
  • 2
    @Theo (and/or whoever also voted to close): Note that there was something of a community consensus at http://meta.math.stackexchange.com/questions/1869/exercising-the-vote-not-to-close to adopt the close-vote tallying system proposed here: http://tea.mathoverflow.net/discussion/506/proposal-for-your-consideration-vote-trading. According to that system, my vote not to close would cancel one of the close votes.2011-05-16
  • 0
    @Qiaochu: How can a Hamiltonian path in the infinite complete graph be finite? Or: How do you prove, that a Hamiltonian path in the finite complete graph has zero or one endpoint(s)?2011-05-16
  • 1
    @Hans: the last sentence should be read "if it has two endpoints, then it is finite and cannot be a Hamiltonian path." A Hamiltonian path in the infinite complete graph either has no endpoints (for example $... -2 \to -1 \to 0 \to 1 \to 2 \to ...$) or it has one endpoint (for example $0 \to 1 \to -1 \to 2 \to ...$). I can't think of a sensible definition which would allow a Hamiltonian path in the infinite complete graph to have two endpoints, and you have provided no examples of such a thing. If it has two endpoints $u_1 \to u_2 \to ... \to u_n$, then it only involves finitely many vertices.2011-05-16
  • 0
    @joriki: I voted to close *before* you posted your first comment, and I agree that we should adhere to that system. I posted my last comment to explain my close vote. I won't participate in this discussion (which should be transferred to meta, IMO) since I'm not interested at all, I made my point. I'll be happy to cast a vote to reopen in case the question gets closed, just ping me. For the moment I'm out.2011-05-16
  • 3
    @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?2011-05-16
  • 2
    Another close vote has been added without anyone noting in a comment that they cancelled my vote not to close. Before adding any further close votes, please read my comments above (and the discussions they link to if you're not familiar with them).2011-05-16
  • 1
    @joriki: I'm doing my best in order to support you in keeping the system working (it appears that it doesn't). But I don't think I can do more at the moment than voting your comments up to make them visible and offering my vote to reopen as I did in a previous comment.2011-05-16

3 Answers 3

8

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.

  • 3
    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.2011-05-16
5

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

  • 0
    Thank you very much for your clarifications!2011-05-16
3

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

  • 0
    Oh, I guess @joriki has seen this idea elsewhere already. Any references?2011-05-16
  • 1
    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: http://www.maa.org/devlin/devlin_01_06.html2011-05-16