The detour matrix 
,
sometimes also called the maximum path matrix or maximal topological distances matrix,
of a graph is a symmetric
matrix whose 
th
entry is the length of the longest path from vertex 
to vertex 
, or 
if there is no such path (Harary 1994, p. 203). The
most common convention (and that adopted here) is to take 
.
For a connected graph, every path extends to a spanning tree. Its detour matrix can
therefore be computed from the distance matrices
of all its spanning trees as 
, where 
ranges over the spanning trees
and 
is the graph
distance in 
(Harary 1994, p. 203).
For a graph with vertex count 
, a detour matrix element of 
corresponds to a Hamiltonian
path between vertices 
and 
. A graph having a detour matrix
whose off-diagonal elements are all equal to 
is therefore Hamilton-connected.
Similarly, a bipartite graph whose elements 
are maximal for all 
and 
corresponding to different elements of the bipartition
is Hamilton-laceable.
For a complete multipartite graph with positive part sizes 
,
, put 
. If distinct endpoints 
and 
belong to parts 
and 
, and 
counts how many of these endpoints belong to part 
, then
 |
Occurrences of a part on a path require separating vertices from other parts, which gives the upper bound. Delete the indicated number of vertices from a part with maximum deficit. The retained
part counts 
satisfy 
,
where 
.
A connected loopless multigraph on the parts with
degrees 
has an Eulerian path
with the prescribed endpoint parts. Its sequence of parts yields a path
attaining the bound. Such a multigraph exists because
no prescribed vertex degree exceeds half their sum.
Only the endpoint parts can have odd vertex degree.
Components can therefore be joined by degree-preserving
edge switches before taking the Eulerian path.
Precomputed detour matrices for many named graphs are available in the Wolfram Language as GraphData[graph, "DetourMatrix"].
