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
    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!2012-03-15
  • 0
    Here, also from [Wikipedia](http://en.wikipedia.org/wiki/Tree_%28graph_theory%29) 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".2012-03-15
  • 0
    @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?2012-03-15
  • 0
    @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).2012-03-15
  • 0
    @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](http://en.wikipedia.org/wiki/Cycle_(graph_theory))); if I understand correctly, your second point was based on a definition of a simple cycle as vertex-disjoint but not necessarily edge-disjoint?2012-03-15
  • 0
    @joriki: I cannot conceive repeating edges without repeating vertices (i.e., being vertex-disjoint but not necessarily edge-disjoint). Can you give an example?2012-03-15
  • 0
    @Marc: I thought your point about "at least three vertices" was based on the idea that there's a cycle between two adjacent vertices that uses each of the vertices only once but uses the edge between them twice. So I was thinking that this problem is excluded if a cycle is required to be edge-disjoint. Perhaps I misunderstood you?2012-03-15
  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2781/discussion-between-marc-van-leeuwen-and-joriki)2012-03-15