Eulerian paths in infinite graphs?

A forum for good logic/math puzzles.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
torne
Posts: 98
Joined: Wed Nov 01, 2006 11:58 am UTC
Location: London, UK

Eulerian paths in infinite graphs?

Postby torne » Thu Mar 15, 2007 12:52 pm UTC

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

User avatar
Yakk
Poster with most posts but no title.
Posts: 11120
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Postby Yakk » Thu Mar 15, 2007 2:46 pm UTC

Code: Select all

A-B
\ /
 C

D-E
\ /
 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.

User avatar
Strilanc
Posts: 646
Joined: Fri Dec 08, 2006 7:18 am UTC

Postby Strilanc » Thu Mar 15, 2007 3:35 pm UTC

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.
Don't pay attention to this signature, it's contradictory.

User avatar
torne
Posts: 98
Joined: Wed Nov 01, 2006 11:58 am UTC
Location: London, UK

Postby torne » Thu Mar 15, 2007 4:46 pm UTC

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

ekim
Posts: 109
Joined: Mon Dec 18, 2006 12:40 pm UTC
Location: Seattle

Re: Eulerian paths in infinite graphs?

Postby ekim » Fri Sep 26, 2014 1:59 am UTC

My intuition here is that a connected infinite graph contains an Eulerian path IFF
(a) all finite connected subgraphs contain an E-path
(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...

User avatar
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?

Postby Yakk » Fri Sep 26, 2014 2:04 am UTC

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.

ekim
Posts: 109
Joined: Mon Dec 18, 2006 12:40 pm UTC
Location: Seattle

Re: Eulerian paths in infinite graphs?

Postby ekim » Fri Sep 26, 2014 2:45 am UTC

Ha! Good to see.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Eulerian paths in infinite graphs?

Postby jaap » Fri Sep 26, 2014 8:43 am UTC

ekim wrote:My intuition here is that a connected infinite graph contains an Eulerian path IFF
(a) all finite connected subgraphs contain an E-path
(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 odd-degree vertices. This is because in choosing a subgraph, some vertices change their degree.

For example this graph has a Eulerian path,

Code: Select all

  o---o
  |\  |
  | o |
  |  \|
  o---o

but if you delete one node you get the following subgraph that is not Eulerian:

Code: Select all

  o---o
  |\
  | o
  |
  o

If you hang an infinitely long string of nodes onto the bottom-right node of the first graph, then you have an infinite graph that is Eulerian, with a finite connected subgraph that is not.

ekim
Posts: 109
Joined: Mon Dec 18, 2006 12:40 pm UTC
Location: Seattle

Re: Eulerian paths in infinite graphs?

Postby ekim » Fri Sep 26, 2014 2:44 pm UTC

Quite right. And the second half isn't true either (to borrow your example for a moment):

Code: Select all

  o---o---o---o...
  |\  |\  |\  |...
  | o | o | o |...
  |  \|  \|  \|...
  o---o---o---o...

User avatar
Lopsidation
Posts: 183
Joined: Tue Oct 27, 2009 11:29 pm UTC

Re: Eulerian paths in infinite graphs?

Postby Lopsidation » Fri Sep 26, 2014 5:43 pm UTC

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.

ekim
Posts: 109
Joined: Mon Dec 18, 2006 12:40 pm UTC
Location: Seattle

Re: Eulerian paths in infinite graphs?

Postby ekim » Sat Sep 27, 2014 1:22 am UTC

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?):

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

User avatar
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:

Postby jestingrabbit » Sat Sep 27, 2014 1:40 am UTC

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 bi-infinite. We can be okay with that.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

ekim
Posts: 109
Joined: Mon Dec 18, 2006 12:40 pm UTC
Location: Seattle

Re: Eulerian paths in infinite graphs?

Postby ekim » Sat Sep 27, 2014 2:29 am UTC

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.

User avatar
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?

Postby jestingrabbit » Sat Sep 27, 2014 5:18 am UTC

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.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Eulerian paths in infinite graphs?

Postby jaap » Sat Sep 27, 2014 5:51 am UTC

(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:
... --o---o---o---o---o--...
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 semi-infinite 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 semi-infinite 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

     |   |   |   
  ---o---o---o---
     |   |   |   
  ---o---o---o---
     |   |   |   
  ---o---o---o---
     |   |   |   

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 semi-infinite components between the spikes.

If you insist that you only allow semi-infinite paths, you can construct an infinite grid with one odd-degree vertex by extending this cube-like graph in all directions:
cube3.png
cube3.png (4.42 KiB) Viewed 4756 times

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 {v1,... vn} where n is odd, and suppose wlog that the path ends at v1. 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:
v1-a-v2-b-v3-a-v4-b-....-a-vn-1-b-vn-a-b-v1
For n=1 there is the trivial empty path.
I think the limit of this inductive process is a e-path 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.

ekim
Posts: 109
Joined: Mon Dec 18, 2006 12:40 pm UTC
Location: Seattle

Re: Eulerian paths in infinite graphs?

Postby ekim » Tue Sep 30, 2014 4:23 am UTC

Nice induction on the complete-naturals-graph.

Another infinite-degree 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.


Return to “Logic Puzzles”

Who is online

Users browsing this forum: No registered users and 8 guests