Tutte path

Graph with a Tutte path highlighted red

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.

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

References

1. Tutte, W. T. (1956). "A theorem on planar graphs" (PDF). Transactions of the American Mathematical Society. 82: 99–116. doi:10.2307/1992980. JSTOR   1992980. MR   0081471.
2. Schmid, Andreas; Schmidt, Jens M. (2017). "Computing Tutte Paths". 34th International Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs). Vol. 66. pp. 57:1–57:14. arXiv: 1707.05994 .