What is difference between cycle, path and circuit in Graph Theory

Question

I am currently studying Graph Theory and want to know the difference in between Path , Cycle and Circuit.

I know the difference between Path and the cycle but What is the Circuit actually mean.

I think it is because various books use various terms differently. What some call a path is what others call a simple path. Those who call it a simple path use the word walk for a path. The same is true with Cycle and circuit. So, I believe that both of you are saying the same thing. What about the length? Some define a cycle, a circuit or a closed walk to be of nonzero length and some do not mention any restriction. A sequence of vertices and edges... could it be empty? I guess things should be standardized in Graph theory. — , Jan 09 '15 at 08:47

score 105 · Accepted Answer · answered Jan 03 '16 at 11:45

105

All of these are sequences of vertices and edges. They have the following properties :

Walk : Vertices may repeat. Edges may repeat (Closed or Open)
Trail : Vertices may repeat. Edges cannot repeat (Open)
Circuit : Vertices may repeat. Edges cannot repeat (Closed)
Path : Vertices cannot repeat. Edges cannot repeat (Open)
Cycle : Vertices cannot repeat. Edges cannot repeat (Closed)

NOTE : For closed sequences start and end vertices are the only ones that can repeat.

answered Jan 03 '16 at 11:45

DollarAkshay

1,209

6

@Nilanjan Dont see anything wrong in it – DollarAkshay Jan 03 '16 at 11:57
6

Thank you for nice and concise answer. I think adding few lines would make your answer better. Circuit = Closed Trail. Cycle = Closed Path. – Md. Abu Nafee Ibna Zahid Mar 06 '18 at 14:43
1

Can trail be not closed? It seems that trial can be closed too, as vertices can repeat? Start and end vertices can be the same vertices to make the trial closed? – Sensebe Nov 01 '18 at 12:57
1

This page seems to be more precise and non ambiguous: http://mathonline.wikidot.com/walks-trails-paths-cycles-and-circuits – Sensebe Nov 01 '18 at 13:02

score 23 · Answer 2 · edited Jul 03 '14 at 04:11

Usually a path in general is same as a walk which is just a sequence of vertices such that adjacent vertices are connected by edges. Think of it as just traveling around a graph along the edges with no restrictions.

Some books, however, refer to a path as a "simple" path. In that case when we say a path we mean that no vertices are repeated. We do not travel to the same vertex twice (or more).

A cycle is a closed path. That is, we start and end at the same vertex. In the middle, we do not travel to any vertex twice.

It will be convenient to define trails before moving on to circuits. Trails refer to a walk where no edge is repeated. (Observe the difference between a trail and a simple path)

Circuits refer to the closed trails, meaning we start and end at the same vertex.

I really dislike definitions such as "a cycle is a closed path". If we take the definition of a path to mean that there are no repeated vertices or edges, then by definition a cycle cannot be a path, because the first and last nodes are repeated. If we're being so pedantic as to create all these terms, then we should be just as pedantic in their definitions. — Louis Sayers, Oct 22 '21 at 04:02

score 12 · Answer 3 · answered Apr 05 '15 at 19:09

Different books have different terminology in some books a simple path means in which none of the edges are repeated and a circuit is a path which begins and ends at same vertex,and circuit and cycle are same thing in these books.

Books which use the term walk have different definitions of path and circuit,here, walk is defined to be an alternating sequence of vertices and edges of a graph, a trail is used to denote a walk that has no repeated edge here a path is a trail with no repeated vertices, closed walk is walk that starts and ends with same vertex and a circuit is a closed trail.

This should probably be the right answer as in the field of graph theory terminology is very not standardized. — Celeritas, Apr 19 '16 at 11:16

score 4 · Answer 4 · answered Nov 15 '14 at 10:52

I think I disagree with Kelvin Soh a bit, in that he seems to allow a path to repeat the same vertex, and I think this is not a common definition. I would say:

Path: Distinct vertices $v_1,\dots,v_k$ with edges between $v_i$ and $v_{i+1}$, $1 \le i \le k-1$.

Trail: A sequence of not necessarily distinct vertices $v_1,\dots,v_k$ and a sequence of edges $e_1,\dots,e_{k-1}$ such that $e_i$ connects $v_i$ and $v_{i+1}$, $1 \le i \le k-1$ and all of the $e_i$ are distinct.

Cycle: Distinct vertices $v_1,\dots, v_k$ with edges between $v_i$ and $v_{i+1}$, $1 \le i \le k-1$, and the edge $\{v_1,v_k\}$.

Circuit: A trail with the same first and last vertex.

Note: In some old texts the word circuit is sometimes used to mean cycle.

score 1 · Answer 5 · answered Nov 15 '14 at 10:31

1

In a circuit we have can repeated vertices, but we cannot in a cycle.

answered Nov 15 '14 at 10:31

Maths student

509

score 0 · Answer 6 · answered Feb 03 '15 at 04:27

0

cycle is a closed path with no vertices repeated.

answered Feb 03 '15 at 04:27

shalu

17

1

Yeah, but then what is a path and what is a circuit? – Mike Pierce Feb 03 '15 at 06:31

Penny Bas · Answer 7 · 2023-12-09T07:00:25.890

it depends on the material you are studying. I have read many articles online that says that a circuit is a closed trail, and a cycle is a closed path, which is correct.

However, the books we use in class says a circuit is a closed path and a cycle is basically a circuit. That is also correct for the context of that material and the theory used by the authors. So make sure to ask your instructor. I you are learning by yourself, I would say stick with a circuit as a closed trail, and a cycle as a closed path.

so, lest start with the terminology:
closed: first and last vertex are the same (starts and ends at the same vertex.)
open: first and last vertex are different (starts and ends at a different vertex on the graph.)
A path is a walk in which no edges and no vertices repeat.
A trail is a walk in which no edges occur more than once, all edges in the walk are unique.
A circuit should be a closed trail, but again, it could be a closed path if that is the proof being studied.
A cycle is always a closed path.

I hope that helped!

What is difference between cycle, path and circuit in Graph Theory

7 Answers7

Linked