Discrete Mathematical Structures by Pearson

10-26 Discrete Mathematical Structures

Figs. 10.33(a) and (b) illustrate two walks in the graph:

v

3

v

4

v

2

v

1

v

5

Figure 10.33(a)

v

3

v

4

v

2

v

1

Figure 10.33(b)

1. v

1

→ v

2

→ v

3

→ v

4

→ v

5

is a walk

2. v

1

→ v

2

→ v

3

→ v

4

→ v

2

is a walk (here vertex v

2

is repeated)

Path: A path is a walk through a sequence of vertices:

v

1

→ v

2

→ v

3

→ … v

n

- 1

→ v

n

without any repetition of vertices such a path is also known as simple path or an elementary path.

In a path, terminal vertices are of degree 1, whereas all the intermediate vertices are of degree 2.

The walk shown in Fig. 10.33(b), that is, v

1

→ v

2

→ v

3

→ v

4

→ v

2

is not a path as vertex v

2

is repeated.

Trail: A walk in ...