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][3]

History and existence

The concept of Tutte paths originated with W. T. Tutte's foundational work in 1977.^[4] Tutte proved a fundamental result about the existence of such paths in planar graphs:

Tutte's Theorem: Let ${\displaystyle G}$ be a 2-connected planar graph with distinct vertices ${\displaystyle X}$ and ${\displaystyle Y}$ on the outer face. Let ${\displaystyle \alpha }$ be an edge on the outer face. Then ${\displaystyle G}$ has a Tutte path from ${\displaystyle X}$ to ${\displaystyle Y}$ that uses edge ${\displaystyle \alpha }$.^[4]

This result guarantees that Tutte paths exist in 2-connected planar graphs with specified endpoints and containing a specified edge, making them a powerful structural tool for analyzing such graphs.

Computational complexity

For many years, it was not known whether Tutte paths could be computed in polynomial time. A significant breakthrough came in 2015 when Schmid and Schmidt showed that Tutte paths in 3-connected planar graphs can be found in polynomial time, with their algorithm running in quadratic time.^[5] This result was later extended to 2-connected planar graphs in 2018.^[2]

In 2019, Biedl and Kindermann made another major advance by showing that Tutte paths can be found in linear time.^[6] Their approach provides a new proof of the existence of Tutte paths in 3-connected planar graphs that is constructive and leads directly to an efficient algorithm. The key insight is to reduce the problem to finding Tutte paths in 3-connected components using SPQR trees, and then to handle 3-connected graphs with a case-by-case analysis based on the structure of cutting pairs and the outer face.

System of distinct representatives

Biedl and Kindermann's construction produces not just a Tutte path, but a Tutte path with a system of distinct representatives (TSDR-path), which is a Tutte path ${\displaystyle P}$ together with an injective function ${\displaystyle \sigma }$ that assigns to each ${\displaystyle P}$-bridge ${\displaystyle C}$ a vertex ${\displaystyle \sigma (C)}$ on ${\displaystyle P}$ that is an attachment point of ${\displaystyle C}$, such that different bridges receive different representatives.^[6] For 3-connected planar graphs, they show that a T_int-path can be found—a TSDR-path that visits all exterior vertices and where the representative ${\displaystyle \sigma (C)}$ is always an interior vertex for every ${\displaystyle P}$-bridge ${\displaystyle C}$.^[6]

This stronger property is particularly useful for applications, as it provides an explicit assignment of which attachment point "represents" each bridge, and guarantees that these representatives do not conflict with each other.

Applications

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.

Tutte paths have been applied to solve several important problems on planar graphs:

• Binary spanning trees: Every 3-connected planar graph has a spanning tree of maximum degree 3 (also called a binary spanning tree). Using Tutte paths with systems of distinct representatives, such trees can be constructed in linear time.^[6]

• 2-walks: A 2-walk of a graph is a walk that visits every vertex at least once and at most twice. Every 3-connected planar graph has a 2-walk, and using the linear-time Tutte path algorithm, such a walk can be found in linear time—improving on the previous best bound of ${\displaystyle O(n^{3})}$.^[6]

See also

• Hamiltonian path problem
• Tait's conjecture
• SPQR tree