Tutte path

Graph with a Tutte path highlighted red

In graph theory, a Tutte path is a path $P$ within a graph $G$ such that every connected component that remains after removing the vertices of $P$ from $G$ is connected back to $P$ at a limited number of vertices.

The precise definition relies on the following terms:

• $P$-bridge: For a given path $P$ in a graph $G$, a $P$-bridge is either a single edge not in $P$ that connects two vertices of $P$, or it is a connected component of the graph remaining after deleting the vertices of $P$, along with all the edges that connect this component to $P$.
• Attachment point: The attachment points of a $P$-bridge are the vertices of the path $P$ that are connected by an edge to a vertex within the $P$-bridge.

A Tutte path then is a path $P$ in $G$ such that every $P$-bridge that remains after removing the vertices of $P$ from $G$ has at most three points of attachment to the path $P$. Furthermore, if a $P$-bridge contains edges from the outer face of the graph (in the context of planar graphs), it is restricted to having at most two attachment points.

A key motivation for the study of Tutte paths is their close relationship to Hamiltonian paths and cycles, paths and cycles in a graph that visit every vertex exactly once. A Tutte path is a relaxation of this concept; it does not require that all vertices be on the path. However, the constraints on the bridges provide strong structural information about the graph which can then be used to find a Hamiltonian path or cycle, especially in planar graphs.

See also

• Hamiltonian path problem
• Tait's conjecture