1
$\begingroup$

Looking for some hint on a question in an assignment

"Find a graph which has some vertices u, v and w such that there is a cycle containing both u and v, a cycle containing both v and w, but no cycle containing both u and w."

I don't get how that is even possible. a cycle containing both u and v, means there are path: u -> v path: v -> u.

a cycle for v and w, means there is path: v -> w path: w -> v

then shouldnt that imply there is a cycle containing u and w. because to get from u to w, we take path u->v, then v->w to get from w to u, we take path w->v, then v->u

I dont get how this question is possible

1 Answers 1

2

Unfortunately, graph theory terminology isn't completely standardized. From Wikipedia:

A path with no repeated vertices is called a simple path, and a cycle with no repeated vertices or edges aside from the necessary repetition of the start and end vertex is a simple cycle. In modern graph theory, most often "simple" is implied; i.e., "cycle" means "simple cycle" and "path" means "simple path", but this convention is not always observed, especially in applied graph theory. Some authors (e.g. Bondy and Murty 1976) use the term "walk" for a path in which vertices or edges may be repeated, and reserve the term "path" for what is here called a simple path.

It appears that your assignment is using "cycle" to mean "simple cycle" whereas you're using the more general definition. Under the more general definition, your argument is correct. However, if "simple" is implied, the existence of a simple cycle containing $u$ and $v$ and of one containing $v$ and $w$ doesn't imply the existence of a simple cycle containing $u$ and $w$ – think of a figure eight with $v$ at the crossing point.

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2781/discussion-between-marc-van-leeuwen-and-joriki)2012-03-15