Math Home

Graph Theory

Let \(G\) be a graph. A cycle in \(G\) is a path \((v_1, p_1, p_2, p_3, \dots, p_k, v_1)\) such that \((v_1, p_1, p_2, p_3, \dots, p_k\) is a simple path.

Informally, a cycle is a loop in the graph.

Let \(G\) be an undirected graph with vertex set \(V = \{1,2,3,4,5,6\}\) and edge set containing \(\{(1,2), (1,3), (1,6), (2,4), (2,5), (4,5), (4,6), (5,6)\}\) and their reverses. An example of a cycle beginning and ending at \(5\) is \((5,6,1,2,5).\) That is, we first go from \(5\) to \(6,\) then \(6\) to \(1,\) then \(1\) to \(2,\) and finally \(2\) to \(5.\) We can draw a picture of the cycle as follows: