From: Douglas W Bass Subject: Re: walking a graph. Date: 6 Apr 1999 05:53:33 GMT Newsgroups: sci.math Keywords: Euler cycles vs Hamiltonian cycles Kelly Trinh! wrote: : Hello, : I was looking at some general interest problems about finding a walk : of a given graph, with the common restriction of not walking over : lines twice.... I was wondering, is it possible for a graph to have : one point, and only one point, with three lines emerging from it? The other responders surmised that you when you say a walk, you mean traversing all the edges without using any edge twice. If you can do that, then the graph is Eulerian, and I've heard the walk called an Euler cycle (after the father of graph theory, Leonhard Euler). Sometimes we only want to visit all the vertices without visiting any vertex twice. That's called a Hamilton cycle. If you have any vertex with degree 1 in a graph, then it doesn't have a Hamilton cycle. There are many known results about Euler cycles and Hamilton cycles in graphs. See well-known texts such as the ones by F. Harary, Bondy and Murty, Gibbons, etc. Best wishes, Douglas Bass ------------------------------------------------------------------------- Douglas Bass Ph.D Student, Computer Science, University of Texas at Dallas Phone: (972)-883-6444 email: dbass@utdallas.edu URL: http://www.utdallas.edu/~dbass The opinions expressed are strictly my own, and are not necessarily those of the faculty or administration of the University of Texas at Dallas.