CS Discrete Math Definitions

Walk

Each vertex is connected to the next by an edge. (You can repeat vertices and edges.)

Open Walk

A walk that starts and ends at different vertices.

Closed Walk

A walk that starts and ends at the same vertex (Ex. A , B, C, A)

Trail

A walk where no edge is repeated but vertices may repeat. (Ex. { A, B, C, A } edges AB, BC, and CA each used once)

Open Trail

A trail that starts and ends at different vertices. (Ex. A,B,C)

Closed Trail = (CIRCUIT)

A trail that starts and ends at the same vertex & no edge is repeated. (Ex. A, B, C, A)

Path

A walk where no vertices and no edges are repeated. (Ex. A,B,C)

Cycle

A path that starts and ends at the same vertex, and has no repeated edges or vertices. (Ex. A, B, C, A)

Circuit

Must have the same vertex at the beginning and end and no repeated edges but can repeat vertices.