Skip to content
Free public beta until December 4, 2026: every course is open, no card needed. After that, the first chapter of each course stays free and full access is a one-time $39 ($19 for up to 100 founding members chosen for helpful feedback). Your progress is kept. How the beta works

Recipe

Determine whether a graph has a cycle

Use when: you have a small graph's edge list and need to know whether it contains a cycle, or how short the shortest one is

Goal: either a shortest cycle traced vertex by vertex, or a solid reason none exists

Taught in Cycles

Quick recipe

  1. Rule out any vertex that can't lie on a cycle
  2. Search for a closed walk with no repeated vertex, shortest length first
  3. Confirm the candidate is a genuine cycle
  1. 1

    Set aside every vertex with degree 1, since a cycle needs two edges at each of its own vertices, and a degree-1 vertex only has one.

    Example

    In edges \{A,B\},\{B,C\},\{C,D\},\{D,B\},\{D,E\}, vertices A and E both have degree 1, leaving only B, C, D to check.

    Why: a vertex contributes to a cycle through two of the cycle's edges meeting there, which a degree-1 vertex has no second edge to supply.

  2. 2

    Starting from a remaining vertex, try to trace a walk back to itself with no vertex repeated along the way, checking length 3 before longer lengths.

    Example

    From B in the graph above, the walk B,C,D,B uses the edges \{B,C\},\{C,D\},\{D,B\} and repeats no vertex but B itself.

    • a closed walk of the current length with no repeats is found — that's a cycle; if it's the shortest length tried, it's the shortest cycle.
    • no such walk exists at the current length from any remaining vertex — try the next length up, or conclude none exists once every remaining vertex is exhausted.

    Why: a cycle's shortest possible length is 3, so checking length 3 first finds the shortest cycle without checking longer walks needlessly.

  3. 3

    Check that each consecutive pair in the walk is an actual edge, that it starts and ends at the same vertex, and that no other vertex repeats.

    Example

    In B,C,D,B, each of \{B,C\}, \{C,D\}, \{D,B\} is a real edge, only B repeats, and it repeats only as the required start and end.

    Why: a walk that revisits a vertex partway through, or uses a pair with no actual edge, isn't the closed loop a cycle requires.

Common mistakes

  • Counting a walk that reuses a vertex in the middle as a cycle, instead of only at the start and end.
  • Checking longer closed walks before ruling out a length-3 cycle first.
  • Forgetting to remove degree-1 vertices before searching, wasting time tracing walks through a vertex that can never be part of one.
  • Concluding a graph is acyclic after failing to find a cycle from just one starting vertex, instead of trying every remaining vertex.