0

- Background information: I am studying graph theory in discrete mathematics. I have come across this question, but my solution contradicts my professor solution, and I don't understand some parts of the provided solution. I need help with reasoning and understanding her answer.

- Original question and professor solution: enter image description here

- My solution:

I think the answer is true because considering a (u,v) path of {(u,x), (x,w), (w,x), (x,v)} , we can easily see that (x,w) and (w,x) exist which prove that (u,v) path passes through w, and contains w.

- My question:

Why does my professor say that the (u,v) path in G does not contain vertex w? And will the (u,v) path pass through vertex w?

Agent 0
  • 669

1 Answers1

1

A path cannot repeat vertices. In the "path" you've written, x is visited twice.

[Edit]

Here is a reference for the path, trail, walk, cycle, and circuit definitions.

What is difference between cycle, path and circuit in Graph Theory

Agent 0
  • 669
Air Conditioner
  • 1,872
  • Yeah, you are right, x is being repeated twice over here, just wondering if w is repeated twice as well? – Agent 0 Jan 17 '18 at 00:36
  • 1
    There are two edges containing w, but w itself is only visited once. Writing out the full vertex-edge sequence shows that your walk is (u, {u, x}, x, {x, w}, w, {w, x}, x, {x,v}, v). – Air Conditioner Jan 17 '18 at 00:39
  • I see that makes sense, path is repeated vertices not repeated edges, so {x,w} and {w,x} does not count. Only vertex x because it is visited two times. – Agent 0 Jan 17 '18 at 00:42
  • Thanks a lot for your clarification, I was just confusing few definitions :) – Agent 0 Jan 17 '18 at 00:43
  • 1
    Well, if you repeat an edge, at least one of its vertices must have been repeated. – Air Conditioner Jan 17 '18 at 00:44
  • Yeah, that is true based on your vertex-edge sequence. Clear explanation. – Agent 0 Jan 17 '18 at 00:47
  • One more question regarding this problem, like (u,v) path, there cannot be a (u,v) walk? I know a walk cannot have repeated edges and we can clearly see that {x,w}, and {w,x} are repeated, so (u,v) walk doesn't exist, am I right? – Agent 0 Jan 17 '18 at 00:59
  • 1
    Walks are usually allowed to repeat edges and vertices. So there is a u-v walk (one of them is actually the "path" you wrote). – Air Conditioner Jan 17 '18 at 02:20
  • Yes, I need to work more on definitions. In case, people are looking for a reference: https://math.stackexchange.com/questions/655589/what-is-difference-between-cycle-path-and-circuit-in-graph-theory/1598203#1598203 – Agent 0 Jan 17 '18 at 02:40