Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Tommy Jensen
Posts:
249
From:
Daegu, Korea
Registered:
12/6/09


Re: Hopcroft & Ullman's book  incomplete definition of a cycle in a graph?
Posted:
Mar 10, 2016 4:52 AM


On Thu, 10 Mar 2016 11:21:01 +0200, Jussi Piitulainen wrote:
> > You are thinking of computer science kind of trees, with a root and > directed connections away from the root, no going back.
That is a good point actually. When they think of a graph, they may well have in mind what is usually called a digraph. in which each edge has a definite direction. The term "graph" has come to be used for the kinds of relations that are symmetric, that is, there are no directions on the edges. If there is an edge from a to b, the same edge is also an edge from b to a. If they do not assume this, then their definition makes perfectly sense. There can be a cycle which is a loop, from a to a, and another cycle which consists of an edge from a to b and another different edge from b to a. So in that case the answer to the original post is that the case of a single vertex should be somehow excluded. There can be no cycle of length zero. The shortest cycles are loops, they join a vertex to itself and have length 1.



