---
tag: 1FP5BQ1E6M
kind: concept
name: Induced path
aliases: [chordless-cycle, graph-antihole, graph-hole, hole-graph-theory, induced-cycle]
sources:
  - wikipedia: en:7714430@r1335627072
    locator: Induced path
    note: adopted
    mention: wikipedia://en/7714430
    sections: [Summary]
same_as:
  wikidata: Q15704639
  wikipedia: Induced path
inventory: [VEPZ6T1PTW]
---

## Summary

In the mathematical area of graph theory, an **induced path** in an undirected graph $G$ is a [[path|03NAMV1DHJ]] that is an [[induced subgraph|0EREPBVG2G]] of $G$. That is, it is a sequence of vertices in $G$ such that each two adjacent vertices in the sequence are connected by an edge in $G$, and each two nonadjacent vertices in the sequence are not connected by any edge in $G$. An induced path is sometimes called a **snake**, and the problem of finding long induced paths in hypercube graphs is known as the snake-in-the-box problem.