Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
oh yea I didn't realize there is a something call simple cycle, I know simple path vs path, but didnt realize this. Thanks a lot! –  user308553 Mar 15 '12 at 8:13
    
Here, also from Wikipedia is a citation that shows that the unadorned "cycle" is often implicitly supposed simple: "A tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree". –  Marc van Leeuwen Mar 15 '12 at 9:42
    
@Marc: I don't understand. Aren't a connected undirected graph without simple cycles and a connected undirected graph without general cycles the same thing? Why does that quote tell us anything about how "cycle" is used? –  joriki Mar 15 '12 at 9:53
    
@joriki: A connected undirected graph on $\{a,b\}$ has a general cycle $a,b,a$, so it wouldn't be a tree under this definition. Nor evidently would any graph with more than one vertex, as one can always take some path and then walk back along it to form a cycle. In fact this example show that the "tree" definition not only assumes cycles to be simple, but also to contain at least three vertices (counting the starting/ending vertex only once). –  Marc van Leeuwen Mar 15 '12 at 10:04
    
@Marc: I understand your first point now. On your second point, though, it seems that "simple cycle" is usually taken to mean not only vertex-disjoint but also edge-disjoint (for instance in Wikipedia); if I understand correctly, your second point was based on a definition of a simple cycle as vertex-disjoint but not necessarily edge-disjoint? –  joriki Mar 15 '12 at 10:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.