Eulerian paths in infinite graphs?
Moderators: jestingrabbit, Moderators General, Prelates
Eulerian paths in infinite graphs?
In a finite graph, if exactly zero or two vertexes have odd degree there exists a Eulerian path (a route which visits each edge exactly once but may not start and end), if all vertexes have even degree there also exists a Eulerian cycle (a Eulerian path which starts and ends at the same vertex).
What about in an infinite graph? Does the same rule apply, or are there more (or less) possibilities? Can an infinite graph contain exactly one vertex of odd degree, and if so, is there a Eulerian path on that graph?
This isn't strictly a logic puzzle, since I don't know the answers (yet). I've been musing on it, though, and have some informal theories, so I'm curious to see what others here might think. Perhaps this is a known problem and my Google powers are merely insufficient
also no, it's not a homework problem, i left school a reasonable time ago
What about in an infinite graph? Does the same rule apply, or are there more (or less) possibilities? Can an infinite graph contain exactly one vertex of odd degree, and if so, is there a Eulerian path on that graph?
This isn't strictly a logic puzzle, since I don't know the answers (yet). I've been musing on it, though, and have some informal theories, so I'm curious to see what others here might think. Perhaps this is a known problem and my Google powers are merely insufficient
also no, it's not a homework problem, i left school a reasonable time ago
 Yakk
 Poster with most posts but no title.
 Posts: 11120
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Code: Select all
AB
\ /
C
DE
\ /
F
All vertexes have even degree, but there is no Eulerian cycle. I think you missed the word "connected".
An infinite graph:
Code: Select all
A_1  A_2  A_3  A_4  ...
Note that it has only one node of odd degree.
It has a Eulerian path.
Another infinite graph:
Code: Select all
A B_1  B_2  ...
\ C_1  C_2  ...
\ D_1  D_2  ...
This contains exactly one node of odd degree. There is no Eulerian path.
Oops, yes, I did miss 'connected'.
The questions I posed were intentionally pretty general; I'd already thought of some cases, but I do feel somewhat retarded for not realising it's obvious you can have one odd vertex.
So, yes, that answers some of them, but is there a way to distinguish infinite graphs which have Eulerian paths/cycles from ones which don't (other than by attempting to find such a path/cycle)?
The questions I posed were intentionally pretty general; I'd already thought of some cases, but I do feel somewhat retarded for not realising it's obvious you can have one odd vertex.
So, yes, that answers some of them, but is there a way to distinguish infinite graphs which have Eulerian paths/cycles from ones which don't (other than by attempting to find such a path/cycle)?
Re: Eulerian paths in infinite graphs?
My intuition here is that a connected infinite graph contains an Eulerian path IFF
(a) all finite connected subgraphs contain an Epath
(b) there doesn't exist a subgraph whose removal partitions the graph into more than one infinite connected component
That sound about right? Is anyone from this thread still a member of the forum? It's been a while for me...
(a) all finite connected subgraphs contain an Epath
(b) there doesn't exist a subgraph whose removal partitions the graph into more than one infinite connected component
That sound about right? Is anyone from this thread still a member of the forum? It's been a while for me...
 Yakk
 Poster with most posts but no title.
 Posts: 11120
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Eulerian paths in infinite graphs?
Nope, nobody here but us chickens.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Eulerian paths in infinite graphs?
Ha! Good to see.
Re: Eulerian paths in infinite graphs?
ekim wrote:My intuition here is that a connected infinite graph contains an Eulerian path IFF
(a) all finite connected subgraphs contain an Epath
(b) there doesn't exist a subgraph whose removal partitions the graph into more than one infinite connected component
That sound about right? Is anyone from this thread still a member of the forum? It's been a while for me...
Maybe I misunderstand, but surely (a) is not even true for finite graphs, as you might be able to choose a subgraph with more than 2 odddegree vertices. This is because in choosing a subgraph, some vertices change their degree.
For example this graph has a Eulerian path,
Code: Select all
oo
\ 
 o 
 \
oo
but if you delete one node you get the following subgraph that is not Eulerian:
Code: Select all
oo
\
 o

o
If you hang an infinitely long string of nodes onto the bottomright node of the first graph, then you have an infinite graph that is Eulerian, with a finite connected subgraph that is not.
Re: Eulerian paths in infinite graphs?
Quite right. And the second half isn't true either (to borrow your example for a moment):
Code: Select all
oooo...
\ \ \ ...
 o  o  o ...
 \ \ \...
oooo...
 Lopsidation
 Posts: 183
 Joined: Tue Oct 27, 2009 11:29 pm UTC
Re: Eulerian paths in infinite graphs?
Not sure what you're getting at, ekim; your example satisfies condition (b), and it has a Eulerian path. That having been said, I think condition (b) should read "there doesn't exist a finite subgraph whose removal partitions the graph into more than one infinite connected component."
It's "obvious" that, if an infinite graph has a Eulerian path, then the start vertex has to have odd degree. (EDIT: or infinite degree, I guess.) I wonder, are these two conditions sufficient? I doubt it, but I can't think of a counterexample.
It's "obvious" that, if an infinite graph has a Eulerian path, then the start vertex has to have odd degree. (EDIT: or infinite degree, I guess.) I wonder, are these two conditions sufficient? I doubt it, but I can't think of a counterexample.
Re: Eulerian paths in infinite graphs?
Yakk's third example, three copies of the naturals joined at zero has exactly one vertex of odd degree (do I understand you right, that this is a counterexample of the type you were looking for?):
And this is sort of a stupid / tautological statement, I think, but seems like where I was going with my initial a/b. Sort of equivalent to "graph G has an e.p. iff we can start one and keep going and eventually cover all of G". Oops.
But it would be nice to say something concise and unexpected about vertex degrees. It just seems hard to do that when a pair of infinite tails ruins everything. My example was meant to mimic that pair of infinite tails (the top and bottom horizontal infinite lines) but connect them in a way that allows an euler path. The graph with just the edges connecting the two (vertical/angled) splits us into two tails, breaks (b).
Code: Select all
A B_1  B_2  ...
\ C_1  C_2  ...
\ D_1  D_2  ...
And this is sort of a stupid / tautological statement, I think, but seems like where I was going with my initial a/b. Sort of equivalent to "graph G has an e.p. iff we can start one and keep going and eventually cover all of G". Oops.
graph G has an euler path IFF exists nested G_1 < G_2 < G_3 < ... s.t. union of all G_i = G, and for fixed v in G_1, for all G_i exists eulerian path with vertex v as its start
But it would be nice to say something concise and unexpected about vertex degrees. It just seems hard to do that when a pair of infinite tails ruins everything. My example was meant to mimic that pair of infinite tails (the top and bottom horizontal infinite lines) but connect them in a way that allows an euler path. The graph with just the edges connecting the two (vertical/angled) splits us into two tails, breaks (b).
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re:
Strilanc wrote:Just consider the integers, with each number being a node connected to its successor and predecessor. Every node has even degree, but there is no Eulerian path.
See, I'd actually say that the obvious is a perfectly fine Eulerian path. We don't really need the path to have a beginning. It can be biinfinite. We can be okay with that.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Eulerian paths in infinite graphs?
I was thinking that this might be a nicer definition for infinite e.path  a map from either N or Z to vertices that hits each edge once.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Eulerian paths in infinite graphs?
ekim wrote:I was thinking that this might be a nicer definition for infinite e.path  a map from either N or Z to vertices that hits each edge once.
Yeah, with e_i and e_{i+1} sharing a vertex.
Can anyone come up with a graph where at least one edge has infinite edges which has an eulerian path? For instance, if you have the natural numbers as the vertices, and you include all the edges, is there an Eulerian path? It seems to me there is...
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Eulerian paths in infinite graphs?
(Note: I started writing this hours ago but forgot to post, so some of it has already been discussed in previous posts)
I think (b) should say that there mustn't be a finite subgraph whose removal results in three or more infinite connected components.
For example, the infinite chain graph:
... ooooo...
It is trivially Euclidean  the graph itself is the Euler path. If you remove some finite subgraph (not necessarily connected), you will have two (semi) infinite components.
But even removing any infinite subgraph will not leave you with three or more infinite components, though I'm not sure of a nice way to prove this right now.
With a semiinfinite chain, removing any subgraph leaves at most one infinite component.
Suppose you had any other infinite Eulerian graph, with nodes of finite degree. Because of its Euler path, you could think of it as the above infinite chain graph (or a semiinfinite chain graph if the path had a starting vertex) where its nodes have been merged some finite number of times. Removing any finite set of nodes is then equivalent to removing only a finite set of nodes from the straight chain, so can still only lead to at most two (or one) infinite components.
You'd think that removing any infinite subgraph would still leave at most two infinite components, but I found this is not the case. For example, the infinite 2D grid graph:
It is not hard to see this is Euclidean. From a vertex, have one end of the infinite path go off in a straight line to the left. The other end of the path goes around one square, then builds a layer of petals around the square, and just keeps going around and around it adding one layer at a time.
You can remove an infinite connected subgraph from this grid graph in such a way as to leave an infinite number of infinite connected components. The removed subgraph could for example be a fishbone shape  one infinite horizontal spine with vertical spikes every other node that are also infinitely long. That leaves semiinfinite components between the spikes.
If you insist that you only allow semiinfinite paths, you can construct an infinite grid with one odddegree vertex by extending this cubelike graph in all directions:
From this Eulerian graph you can similarly remove a connected infinite subgraph to create an infinite number of infinite connected components.
If you allow nodes with infinite degree, I suspect there will be even more weirdness.
Edit to add:
I agree that it does. Suppose you have a path that completely covers all the edges of the complete graph on n nodes {v_{1},... v_{n}} where n is odd, and suppose wlog that the path ends at v_{1}. If you add two more nodes a and b and all the edges to make it a larger complete graph, then you can easily extend that first path as follows:
v_{1}av_{2}bv_{3}av_{4}b....av_{n1}bv_{n}abv_{1}
For n=1 there is the trivial empty path.
I think the limit of this inductive process is a epath for the complete graph on the set of nodes labelled by the natural numbers, because for any edge in that graph the path above reaches it in a finite number of steps.
I think (b) should say that there mustn't be a finite subgraph whose removal results in three or more infinite connected components.
For example, the infinite chain graph:
... ooooo...
It is trivially Euclidean  the graph itself is the Euler path. If you remove some finite subgraph (not necessarily connected), you will have two (semi) infinite components.
But even removing any infinite subgraph will not leave you with three or more infinite components, though I'm not sure of a nice way to prove this right now.
With a semiinfinite chain, removing any subgraph leaves at most one infinite component.
Suppose you had any other infinite Eulerian graph, with nodes of finite degree. Because of its Euler path, you could think of it as the above infinite chain graph (or a semiinfinite chain graph if the path had a starting vertex) where its nodes have been merged some finite number of times. Removing any finite set of nodes is then equivalent to removing only a finite set of nodes from the straight chain, so can still only lead to at most two (or one) infinite components.
You'd think that removing any infinite subgraph would still leave at most two infinite components, but I found this is not the case. For example, the infinite 2D grid graph:
Code: Select all
  
ooo
  
ooo
  
ooo
  
It is not hard to see this is Euclidean. From a vertex, have one end of the infinite path go off in a straight line to the left. The other end of the path goes around one square, then builds a layer of petals around the square, and just keeps going around and around it adding one layer at a time.
You can remove an infinite connected subgraph from this grid graph in such a way as to leave an infinite number of infinite connected components. The removed subgraph could for example be a fishbone shape  one infinite horizontal spine with vertical spikes every other node that are also infinitely long. That leaves semiinfinite components between the spikes.
If you insist that you only allow semiinfinite paths, you can construct an infinite grid with one odddegree vertex by extending this cubelike graph in all directions:
From this Eulerian graph you can similarly remove a connected infinite subgraph to create an infinite number of infinite connected components.
If you allow nodes with infinite degree, I suspect there will be even more weirdness.
Edit to add:
jestingrabbit wrote:Can anyone come up with a graph where at least one edge has infinite edges which has an eulerian path? For instance, if you have the natural numbers as the vertices, and you include all the edges, is there an Eulerian path? It seems to me there is...
I agree that it does. Suppose you have a path that completely covers all the edges of the complete graph on n nodes {v_{1},... v_{n}} where n is odd, and suppose wlog that the path ends at v_{1}. If you add two more nodes a and b and all the edges to make it a larger complete graph, then you can easily extend that first path as follows:
v_{1}av_{2}bv_{3}av_{4}b....av_{n1}bv_{n}abv_{1}
For n=1 there is the trivial empty path.
I think the limit of this inductive process is a epath for the complete graph on the set of nodes labelled by the natural numbers, because for any edge in that graph the path above reaches it in a finite number of steps.
Re: Eulerian paths in infinite graphs?
Nice induction on the completenaturalsgraph.
Another infinitedegree vertex graph with an Euler path would be a slightly modified star, where for vertices Z, 0 is connected to everyone, and x is connected to x. Lots of triangles around zero.
Another infinitedegree vertex graph with an Euler path would be a slightly modified star, where for vertices Z, 0 is connected to everyone, and x is connected to x. Lots of triangles around zero.
Who is online
Users browsing this forum: No registered users and 8 guests