Cycle notion in common tree definitions as undirected graphs

31 Views Asked by At

I have found definitions of trees as "undirected graphs that are connected and have no cycles" in multiple textbooks and references. However, none of them seem to offer a clear understanding of what notion of cycles underlies this definition.

What is the correct interpretation of cycles in these definitions? No repeated vertices? No repeated edges? Simple cycles?

1

There are 1 best solutions below

2
On BEST ANSWER

A closed walk is a set of vertices $(v_1,v_2,...,v_n,v_1)$ such that $v_i$ is adjacent to $v_{i+1}$ for $1 \leq i \leq n-1$, and $v_n$ is adjacent to $v_1$.

The edges of a closed walk are the edges $v_iv_{i+1}$ for $1 \leq i \leq n-1$, and the edge $v_nv_1$.

A cycle is a closed walk with no repeated vertices, besides $v_1$, and no repeated edges. This is the definition you want. If you allow for repeated edges in the definition of cycles for a tree, then the closed walk $(v_1, v_2, v_1)$ would constitute a cycle, but this would be contained in the graph of any tree with at least two vertices.