1

I'm reading this paper, and I need some help with clarifying what exactly is the difference between cycle and circuit:

A cycle in an undirected graph is a subgraph in which every vertex has even degree. A cycle is a circuit if it is connected and every one of its vertices has degree two.

The subgraph of a graph $G = (V,E)$, by their definition, is $G' = (V',E')$ where $V' \subseteq V$ and $E' \subseteq E$.
Question 1: Does degree in this statement mean the degree in $G$ or the subgraph $G'$? Neither really makes sense, for example with the following: enter image description here

In the first example, (2)-(3)-(4) is clearly a cycle (at least as taught in any intro CS course). If we take it as a subgraph, then all of its vertices have even degrees in the subgraph, so it seems that the "even degree" definition applies to the subgraph $G'$. However, in the second example, (2)-(3)-(4)-(5) wouldn't be a cycle by this definition, since (2) and (4) have degree 3 in the subgraph marked in red, but this feels very weird to me. Similarly, if the "even degree" definition applies to the original $G$, then the first example wouldn't be a cycle since both (2) and (4) have degree 3.

Question 2: By this definition, $circuits \subset cycles$. Intuitively, is circuit the "simplest" cycle (only one "loop" in the subgraph $G'$)?

To further confuse myself, I saw this post,

Circuit : Vertices may repeat. Edges cannot repeat (Closed)
Cycle : Vertices cannot repeat. Edges cannot repeat (Closed)

Question 3: Now, $cycles \supset circuits$?

Any help clarifying this would be appreciated.

user594147
  • 173
  • 1
    Going by Figure 2 in the same paper, the degree is in the subgraph. – Randy Marsh Aug 28 '20 at 00:09
  • 1
    In your example the subgraph ${23,24,34,25,45}$ isn't a cycle but ${23,34,25,45}$ is. – Randy Marsh Aug 28 '20 at 00:12
  • For Q3, the definitions in that post are for various types of walks, not for graphs. In a cycle walk you can traverse each vertex exactly once, in a circuit walk you can traverse a vertex many times. – Randy Marsh Aug 28 '20 at 00:27
  • Makes sense, thanks a lot! – user594147 Aug 28 '20 at 05:11
  • Actually, could you elaborate a little further on the difference between a walk and a graph? My understanding is that a walk from that post is still a subgraph as defined in that paper. – user594147 Aug 28 '20 at 20:05
  • A walk is a sequence $(e_n)$ of edges in a graph such that $e_n$ and $e_{n+1}$ have a common vertex. Take the triangle graph ${e_1=12,e_2=23,e_3=13}$. Then $(e_1,e_2,e_3)$ is a walk that is a circuit and a cycle, but $(e_1,e_2,e_3,e_2,e_3)$ is a walk that is not a circuit or a cycle. $(e_1,e_1)$ is also a walk that is not a circuit or a cycle. See https://en.wikipedia.org/wiki/Path_(graph_theory) and https://en.wikipedia.org/wiki/Cycle_(graph_theory) – Randy Marsh Aug 28 '20 at 20:22

0 Answers0