5.5: Cycles
- Page ID
- 88872
Terminology
A graph is a circuit, or closed walk, if and only if the vertices can be labeled \(v_0, v_1, \ldots, v_k\) such that \(\{v_j,v_{j+1}\}\) is an edge for all \(j\) and \(v_0=v_k.\)
A graph is a cycle if and only if it is a circuit such that no vertex is used twice.
A cycle on \(n\) vertices is denoted \(C_n.\) Like walk and path terminology for cycles varies widely.
A circuit is Eulerian if and only if it uses every edge in the graph and no edge is used twice.
A circuit is Hamiltonian if and only if it uses every vertex in that graph and no edge is used twice.
Practice
Checkpoint \(\PageIndex{5}\)
Draw a cycle of length 4. Note this is denoted \(C_4.\)
Checkpoint \(\PageIndex{5}\)
Find a circuit that is not a cycle in Figure \(\PageIndex{6}\)
Checkpoint \(\PageIndex{7}\)
Determine which graphs in Figure 5.2.43 have Eulerian circuits.
Checkpoint \(\PageIndex{9}\)
Determine which graphs in Figure 5.2.43 have Hamiltonian circuits.