Paths and Cycles

• A node sequence with is a walk if for . Node is the origin of the walk and node is the destination. Nodes are intermediate nodes. The walk has length k. The walk can also be represented by its edges: , where . For example, in figure 1, we have the walk , , , , .
• A walk is called a path if there are no node repetitions. For example, in figure 1, we have the path , , , .
• A walk is closed if . For example, in figure 1, we have the closed walk , , , , , .
• A closed walk is a cycle or circuit if and is a path. For example, in figure 1, we have the cycle , , , .
• A graph is acyclic if it contains no cycles.
• The length of a cycle is the number of edges in the cycle. Exercise: Show that a graph is bipartite if and only if it contains no cycles of odd length.