Re: Eulerian path in infinite graph

From: David Eppstein (eppstein_at_ics.uci.edu)
Date: 03/08/04 

Date: Mon, 08 Mar 2004 14:26:11 -0800

In article <c2ii6s$1t3kv9$1@ID-218953.news.uni-berlin.de>,
 Rogério Brito <rbrito@ime.usp.br> wrote:

> Unfortunately, I'm having a hard time with one of the exercises, which
> asks for the reader to show that the infinite square grid is an Eulerian
> graph by showing an explicit two-way Eulerian path (i.e., one path that
> covers every edges of the graph and that extends in both directions).
>
> Where can I find a hint for this excercise?

Hint: spiral.

It's not especially difficult if you just start drawing some pictures.
Just make sure both ends of the path are always on the boundary of the
region you've already covered. 

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science

Relevant Pages

  • Re: help.. making an undirected graph directed...
    ... >> A finite graph G is Eulerian if and only if all its vertex degrees are ... >> odd degree, it can't be Eulerian. ... an Eulerian path in a graph is a path that uses each ...
    (comp.programming)
  • Re: help.. making an undirected graph directed...
    ... > Could someone help me solve the following problem: Given a graph G, ... > directioning which has to be done. ... A finite graph G is Eulerian if and only if all its vertex degrees are ... except that for u!= v the edge leaving u in T must come ...
    (comp.programming)
  • Re: Eulerian Graph
    ... an eulerian graph is a graph containing an eulerian ... An eulerian circuit ... connected graph with no loops or multiple edges. ...
    (sci.math)
  • Paint a graph
    ... can anybody give me any hint on where to find anything on painting a graph in ... into say a panel for instance? ...
    (microsoft.public.dotnet.vjsharp)
  • Re: graph theory proof hint needed please
    ... Bill J ... I thought the number of edges at any node would be n-1. ... The number of edges for the whole graph would be! ... Another hint would be great too! ...
    (sci.math)