Tutte path

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

Graph with a Tutte path highlighted red

The precise definition relies on the following terms:^[1]

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

A Tutte path then is a path ${\displaystyle P}$ in ${\displaystyle G}$ such that every ${\displaystyle P}$-bridge that remains after removing the vertices of ${\displaystyle P}$ from ${\displaystyle G}$ has at most three points of attachment to the path ${\displaystyle P}$. Furthermore, if a ${\displaystyle 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.^[2]

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