Induced path

Summary

In the mathematical area of graph theory, an induced path in an undirected graph $G$ is a path that is an induced subgraph 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.