1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What do you mean by repeated edges if a closed walk is a set of vertices? I understand what you are saying, but is precisely lack of formalism what motivated this question. Thanks! $\endgroup$ – Simón Ramírez Amaya Sep 10 '18 at 3:43
  • $\begingroup$ I clarified my meaning by editing the answer. I hope that helps $\endgroup$ – JockoCigarNab Sep 10 '18 at 4:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.