[Math] Find the number of paths of length 3 in a cycling graph.

discrete mathematicsgraph theory

Given a non-oriented graph G where $v_1$, $v_2$ and $v_3$ form a triangle (cycle) and $v_3$ is connected to $v_4$

Considering there is a cycle in the graph and the graph is non oriented, would $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_1$ and $v_1 \rightarrow v_3 \rightarrow v_2 \rightarrow v_1$ be considered 2 distinct paths? What about $v_1 \rightarrow v_2 \rightarrow v_3 \rightarrow v_1$ and $v_2 \rightarrow v_3 \rightarrow v_1 \rightarrow v_2$, it's the same cycle, but with a different starting/ending point.

Best Answer

https://en.wikipedia.org/wiki/Path_(graph_theory)

A path is a sequence of edges which connect a sequence of vertices which, by most definitions, are all distinct from one another.

So $v_1$ would not appear twice in a path (we would call that a cycle), but you'd have to name the edges to define a path.

$v_1v_2$ would equal $v_2v_1$ since it is the same edge.

$v_1v_2v_3$ would be a different path then $v_1v_3v_2$ since the edge sequence is different.

(By these definitions I'd say you have 4 distinct paths)

Related Question