Equivalently, is there a graph that contains an infinite simple path that has a start and an end point? My intuition is that there is no such graph, but I'm finding it hard to articulate why.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ arxiv.org/abs/1004.0110 might be relevant. $\endgroup$– Qiaochu YuanCommented Apr 28, 2010 at 23:12
-
3$\begingroup$ Apologies for a dumb question, but can you give a rigorous self-contained definition of "simple path"? $\endgroup$– Dan PiponiCommented Apr 28, 2010 at 23:32
-
$\begingroup$ @Qiaochu Very interesting stuff! If the short answer is "no", this looks like the long answer. :) $\endgroup$– Aleks KissingerCommented Apr 29, 2010 at 12:29
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
One reasonable definition of "simple path" is a connected acyclic subgraph with vertex degree at most two. But, to avoid circularity, we need a definition for being connected. I think the standard definition is that a subgraph is connected iff every two vertices are at a finite distance from each other, so with this definition the answer is trivially no.
On the other hand, if you define a "simple path" to be an acyclic graph in which all vertices have degree one or two and at most two of them have degree one (not the definition I'd choose, but it works for finite graphs) then with this definition the answer is yes: remove a single vertex from the middle of the double-ended infinite path indexed by the integers.
So the answer to your question depends on the details of your definitions.
answered Apr 29, 2010 at 0:02
-
6$\begingroup$ Wikipedia defines "simple path" in terms of "path", and "path" in terms of "walk" and "walk" in terms of "sequence" at which point my walk through the space of graph theoretical definitions comes to an undefined end. $\endgroup$ Commented Apr 29, 2010 at 0:28
-
4$\begingroup$ Proof that Wikipedia is not wellfounded! :) $\endgroup$ Commented Apr 29, 2010 at 0:35
-
$\begingroup$ Thank you for your response. The second definition above demonstrates that it doesn't really make sense to talk about connectedness via infinite paths. For instance the example you gave is the direct sum of two non-empty graphs (one-ended infinite chains), so it seems counter-intuitive to call it connected. $\endgroup$ Commented Apr 29, 2010 at 10:43
-
$\begingroup$ @François, one can change that though at wikimediafoundation.org/wiki/Support_Wikipedia/en ! :) $\endgroup$ Commented Apr 29, 2010 at 20:26
-
2$\begingroup$ @Mariano, I wish the Axiom of Foundation stated that mathematics should be wellfunded :) $\endgroup$ Commented Apr 29, 2010 at 22:04
$\begingroup$
$\endgroup$
0
I think this is actually a pretty interesting question, so I'm not sure why it has been voted down. Let me briefly expand on Qiaochu's comment. Suppose I ask the related question:
Does the notion of an infinite cycle in an infinite graph G make sense?
Essentially, the answer is no in the graph G itself. However, it turns out that if we add extra points to G by suitably compactifying then the answer is yes. This is the approach taken by Diestel and Bruhn. It turns out that the cycles we obtain after compactifying are well-behaved in the sense that they still satisfy some basic properties that finite cycles in finite graphs do.
A different approach is to start with the notion of cycle itself and ask which kinds of objects have a reasonable notion of cycles. It turns out that graph-like spaces are a rich source of such objects. Indeed, this line of work can be viewed as a generalization of the Diestel and Bruhn approach, since the Freudenthal compactification of a locally finite infinite graph is a graph-like space. Finite graphs are also graph-like spaces, and there are graph-like spaces which do not arise by compactifying infinite graphs.
answered Apr 29, 2010 at 20:07