1
$\begingroup$

A graph $G$ is an ordered pair $(V,E)$ of disjoint sets where $$E\subset V^{\underline{2}}:=\left\{\{x,y\}\ |\ x,y\in V\land x\ne y\right\}.$$


Let $G=(V,E)$ be a graph. A path $P$ in $G$ is an ordered list of elements of $V$ $$P=(x_0,x_1,\ldots x_n)$$ for some $1\leq n$ such that $\{x_{i-1},x_i\}\in E$ for all $1\leq i\leq n$. We call $n$ the length of the path $P$.


Let $G=(V,E)$ be a graph. A cycle is a path $(x_0,x_1,\ldots,x_n)$ such that $x_i\ne x_j$ for all $i\ne j\in[0,n-1]$ and $x_0=x_n$. Note that a cycle has length at least 3.

Why do these definitions imply that a cycle must have a length of at least 3? For example, let $V:=\{a,b\}$ where $a\ne b$. Write $x_0:=a$, $x_1:=b$ and $x_2:=a$. Then $(x_0,x_1,x_2)$ is a path of length 2 which satisfies the definition of cycle.

$\endgroup$
1
  • 1
    $\begingroup$ You're totally right. Take the note as part of the definition. $\endgroup$
    – Berci
    Commented Nov 18, 2020 at 21:19

1 Answer 1

1
$\begingroup$

This is not stated as it is written here, but it is conventional in most definitions of a path that each vertex in the path is distinct (except perhaps the end points if it forms a cycle). This also implies that each edge is distinct, and why it is noted that a cycle must have length at least 3. The way this definition of a path is written is more consistent with the definition of a walk, where revisiting a vertex is allowed.

$\endgroup$
1
  • $\begingroup$ For $n\gt2$ a closed walk of length $n$ with $n$ distinct vertices must also have $n$ distinct edges. This implication does not seem to hold when $n=2$. Maybe it should have been stated explicitly in the definition. $\endgroup$
    – bof
    Commented Nov 19, 2020 at 0:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .