%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2025}
\articlenumber{50}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}
\usepackage{amsfonts,mathrsfs,mathtools,graphics}
%% WARNING: class file loads {enumitem} with conflicts with {enumerate}
\usepackage{bm,dsfont,soul}
\usepackage{lipsum}
\usepackage{tikz-cd}
\usetikzlibrary{positioning,arrows,scopes}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}
\theoremstyle{definition}
\newtheorem{prob}[thm]{Problem}
\newtheorem{ques}[thm]{Question}
\newtheorem{dfn}[thm]{Definition}
\newtheorem{egin}[thm]{Example}
\newenvironment{eg}
  {\pushQED{\qed}\renewcommand{\qedsymbol}{$\diamond$}\egin}
  {\popQED\endegin}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{conj}[thm]{Conjecture}

\newcommand{\CC}{\mathbb{C}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\cO}{\mathcal{O}}
\newcommand{\cU}{\mathcal{U}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cC}{\mathcal{C}}
\newcommand{\cE}{\mathcal{E}}

% indicator function
\newcommand{\one}{\mathds{1}}
% bold one
\newcommand{\bone}{\mathbf{1}}
\newcommand{\boldm}{\mathbf{m}}
\newcommand{\boldmu}{\bm{\mu}}
\newcommand{\boldn}{\mathbf{n}}
\newcommand{\boldu}{\mathbf{u}}
% weighted distance matrix
\newcommand{\Da}{{D^{(\alpha)}}}
% weighted laplacian matrix
\newcommand{\La}{L^{(\alpha)}}

% spanning trees
\newcommand{\trees}{\mathcal{F}_1}
\newcommand{\forests}{\mathcal{F}}
\newcommand{\treecount}{\kappa_1}
\newcommand{\forestcount}{\kappa}
\renewcommand{\Re}{\mathrm{Re}}
\newcommand{\dsp}{\displaystyle}
% \newcommand{\pderiv}[1]{\frac{\partial}{\partial{#1}}}
\newcommand{\angles}[1]{\langle {#1} \rangle}
\newcommand{\degout}{\deg^o}
\DeclareMathOperator{\indeg}{indeg}
\newcommand{\coweight}[1]{w(\overline{#1})}
\newcommand{\display}{\displaystyle}
% matrix transpose
\newcommand{\tr}{\intercal}
% sum of cofactors
\DeclareMathOperator{\cof}{cof}
% convex hull of vertex set
\DeclareMathOperator{\conv}{conv}
\DeclareMathOperator{\energy}{\cE}
\DeclareMathOperator{\supp}{supp}


%% define your title in the usual way
\title[Minors of tree distance matrices]{Principal minors of tree distance matrices (extended abstract)}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
%% for more than 3 names, use the Oxford comma: One Author, Two Author, Red Author, \and Blue Author
\author[Richman, Shokrieh, Wu]
	{Harry Richman\thanks{
		\href{mailto:hrichman@ncts.ntu.edu.tw}{hrichman@ncts.ntu.edu.tw}. 
		H. R. was partially supported by the Howard Hughes Medical Institute and the Matsen Group at the Fred Hutchinson Cancer Center.
		F. S. was partially supported by NSF CAREER grant DMS-2044564.
		C. W. was partially supported by Simons Collaboration Grant 850685.
	}\addressmark{1}, 
	Farbod Shokrieh\addressmark{2}, 
	\and 
	Chenxi Wu\addressmark{3}}

%% then use \addressmark to match authors to institutions here
\address{
	\addressmark{1}Mathematics Division, National Center for Theoretical Sciences, Taipei, Taiwan \\ 
	\addressmark{2}Department of Mathematics, University of Washington, Seattle, USA \\
	\addressmark{3}Department of Mathematics, University of Wisconsin, Madison, USA
}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
    Suppose \texorpdfstring{$D$}{D} is the distance matrix of a tree. 
    Graham and Pollack showed that the determinant of \texorpdfstring{$D$}{D} satisfies a surprising identity
    that depends only on the number of vertices in the given tree.
    We generalize this result to a combinatorial identity for the determinant of
    any principal submatrix of \texorpdfstring{$D$}{D}.
    This new identity involves counts of spanning forests and is proved by use of potential-theoretic concepts on graphs.
}

%% put your French abstract here, or comment this out if you don't have one
% \resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{tree, distance matrix, potential theory, spanning forest}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex, giveninits]{biblatex}
\addbibresource{tree-distance-minors-ref.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above

\section{Introduction}

% \subsection{Path distance}
For two vertices $u, v$ in a connected graph $G$, the {\em path distance} $d(u, v)$ is the number of edges on a shortest path from $u$ to $v$.
For brevity, we will use ``distance'' to mean path distance in this article.
The {\em distance matrix} of $G$ is the matrix $D \in \RR^{V \times V}$ whose $(u, v)$-entry is the distance $d(u, v)$.

As a combinatorialist, perhaps inspired by the matrix-tree theorem, one may ask:
\begin{ques}\label{ques:2}
    Is there any combinatorial information encoded in the determinant of the distance matrix of a graph?
\end{ques}

\begin{eg}
Suppose that $G$ is the tree shown below in \Cref{fig:tree-1}.
\begin{figure}[ht]
    \centering
    \begin{tikzpicture}
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \draw (1) -- (A) -- (B) -- (C) -- (4);
        \draw (A) -- (2);
        \draw (3) -- (B);
        
        \node[left=2pt] at (1) {$v_4$};
        \node[left=2pt] at (2) {$v_5$};
        \node[left=2pt] at (3) {$v_6$};
        \node[right=2pt] at (4) {$v_7$};
        \node[above=2pt] at (A) {$v_1$};
        \node[above=2pt] at (B) {$v_2$};
        \node[above=2pt] at (C) {$v_3$};
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill[black] (\c) circle (2pt);
        }
    \end{tikzpicture}
    \caption{Tree with seven vertices and four leaves.}
    \label{fig:tree-1}
\end{figure}

Using the ordering indicated by the vertex labels, the tree $G$ has distance matrix
\[
    D = \begin{pmatrix}
        0 & 1 & 2 & 1 & 1 & 2 & 3 \\
        1 & 0 & 1 & 2 & 2 & 1 & 2 \\
        2 & 1 & 0 & 3 & 3 & 2 & 1 \\
        1 & 2 & 3 & 0 & 2 & 3 & 4 \\
        1 & 2 & 3 & 2 & 0 & 3 & 4 \\
        2 & 1 & 2 & 3 & 3 & 0 & 3 \\
        3 & 2 & 1 & 4 & 4 & 3 & 0
    \end{pmatrix}.
\]
By direct computation, this matrix has determinant $\det D = 192$.
\end{eg}
    
A result of Graham and Pollak~\cite{graham-pollak} states that if $G$ is a tree with $n$ vertices, then its distance matrix $D$ satisfies
\begin{equation}\label{eq:full-det}
    \det D = (-1)^{n-1} 2^{n - 2} (n - 1).
\end{equation}
This remarkable identity says that when $G$ is a tree, essentially no combinatorial information from $G$ is retained in $\det D$.
Thus in this case, the answer to Question~\ref{ques:2} is an emphatic ``no''!

\subsection{Distance submatrices}

If we are optimistic that there is interesting combinatorics hidden somewhere within the distance matrix $D$, despite the Graham--Pollak identity~\eqref{eq:full-det}, then we could next consider its minors, i.e., determinants of submatrices.
% If $M$ is a square matrix whose rows and columns are indexed by $I$, then for any subset $S \subset I$ we let $M[S]$ denote the matrix obtained from keeping the $S$-indexed rows and columns of $M$.
For a vertex subset $S \subset V(G)$ of a graph $G$, let $D[S]$ denote the submatrix consisting of the $S$-indexed rows and columns of $D$.

\begin{ques}\label{ques:3}
    Is there any combinatorial information encoded in the determinant of the distance {\em submatrix} $D[S]$ of a graph?
\end{ques}

Our main contribution answers ``yes'' to Question~\ref{ques:3} when the graph is a tree, in the form of the following theorem.

\begin{thm}[{\cite[Theorem A]{richman-shokrieh-wu-3}}]
\label{thm:main}
Suppose $G$ is a tree with $n$ vertices, 
and distance matrix $D$.
Let $S \subset V(G)$ be a nonempty subset of vertices.
Then
\begin{equation}\label{eq:main}
    \det D[S] = (-1)^{|S| - 1} 2^{|S| - 2} \left( (n-1)\, \treecount(G;S) - \sum_{\mathcal F_2(G;S)} \left(\degout(F,*) - 2\right)^2  \right),
\end{equation}
where 
$\treecount(G;S)$ is the number of $S$-rooted spanning forests of $G$,
$\forests_2(G;S)$ is the set of $(S,*)$-rooted spanning forests of $G$,
and
$\degout(F,*)$ is the outdegree of the floating component of~$F$.
%the number of edges from the $*$-component of $F$ to a different component. 
\end{thm}

% Given a set of vertices $S = \{v_1, v_2, \ldots, v_r\}$,
Here, an {\em $S$-rooted spanning forest} of $G$ 
means a spanning forest in which each connected component has exactly one vertex of $S$.
An {\em $(S,*)$-rooted spanning forest} of $G$ is a spanning forest which has $|S|+1$ components, where $|S|$ components each contain one vertex of $S$, and the additional component is disjoint from $S$.
We call the component disjoint from $S$ the {\em floating component}, following terminology in \cite{kassel-kenyon-wu}.
We 
% let $F(s)$ denote the $s$-component of $F$, and additionally 
let $F(*)$ denote the floating component
of an $(S,*)$-rooted spanning forest.
% $F \in \forests_2(G; S)$
% (We may refer to the floating component as the $*$-component of $F$.)
If $G$ is the tree in \Cref{fig:tree-1} and $S$ is the set of four leaf vertices, 
then the $S$-rooted spanning forests are shown in \Cref{fig:1-forests},
and the $(S, *)$-rooted spanning forests are shown in \Cref{fig:2-forests}.

% Given a vertex $s$ and a forest $F$,
% % in $\trees(G; S)$, 
% we let $F(s)$ denote the $s$-component of $F$.

\begin{figure}[ht]
    \centering
    % LABEL 123
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw[dotted] (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 124
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw[dotted] (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 125
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw (B) -- (3);
        \draw[dotted] (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 126
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);
    \end{tikzpicture}
    \\[1.5em]
    % LABEL 136
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 146
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 156
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw (B) -- (3);
        \draw (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 235
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw (B) -- (3);
        \draw[dotted] (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 236
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);
    \end{tikzpicture}
    \\[1.5em]
    % LABEL 245
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw (B) -- (3);
        \draw[dotted] (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 246
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 356
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw (B) -- (3);
        \draw (C) -- (4);
    \end{tikzpicture}
    \qquad
    % LABEL 456
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw (B) -- (3);
        \draw (C) -- (4);
    \end{tikzpicture}
    \caption{All forests in $\trees(G;S)$, with vertices in $S$ bolded.}
    \label{fig:1-forests}
\end{figure}

Given a connected subgraph $H \subset G$, the {\em outdegree} $\degout(H)$ of $H$ is the number of edges which have one endpoint in $H$ and the other endpoint outside $H$.
(The outdegree does not depend on edge orientation.)
In \Cref{fig:2-forests}, the forests are grouped according to the outdegree of the floating component; 
the floating component may have outdegree two (top row), outdegree three (lower left), or outdegree four (lower right).
% For definitions of $(S,*)$-rooted spanning forests and other terminology, see \Cref{sec:forest-terminology}.


% ex figure: all extra-component spanning forests
\begin{figure}[ht]
    \centering
    % LABEL 13
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (C) -- (C);
    \end{tikzpicture}
    \qquad
    % LABEL 14
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (C) -- (C);
    \end{tikzpicture}
    \qquad
    % LABEL 15
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (C) -- (C);
    \end{tikzpicture}
    \qquad
    % LABEL 35
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (C) -- (C);
    \end{tikzpicture}
    \qquad
    % LABEL 45
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (C) -- (C);
    \end{tikzpicture}
    \\[3.0em]
    % LABEL 23
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (B) -- (C);
    \end{tikzpicture}
    \qquad
    % LABEL 24
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (B) -- (C);
    \end{tikzpicture}
    \qquad
    % LABEL 25
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (A) -- (A);
    \end{tikzpicture}
    \qquad\qquad\qquad
    % LABEL 12
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw[dotted] (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (A) -- (C);
    \end{tikzpicture}
    \\[1.5em]
    % LABEL 56
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw (B) -- (3);
        \draw (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (A) -- (A);
    \end{tikzpicture}
    \qquad
    % LABEL 26
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (A) -- (A);
    \end{tikzpicture}
    \qquad
    % LABEL 36
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (B) -- (B);
    \end{tikzpicture}
    \qquad
    % LABEL 46
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw[dotted] (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (B) -- (B);
    \end{tikzpicture}
    \qquad\qquad\qquad
    % LABEL 16
    \begin{tikzpicture}[scale=0.4]
        \coordinate (1) at (-0.5,-1);
        \coordinate (2) at (0.5,-1);
        \coordinate (3) at (2,-1);
        \coordinate (4) at (3.5,-1);
        \coordinate (A) at (0,0);
        \coordinate (B) at (1.5,0);
        \coordinate (C) at (3,0);
    
        \foreach \c in {1,2,3,4,A,B,C} {
            \fill (\c) circle (2pt);
        }
        \foreach \c in {1,2,3,4} {
            \draw (\c) circle (3pt);
        }

        \draw (A) -- (B);
        \draw[dotted] (B) -- (C);
        \draw[dotted] (A) -- (1);
        \draw[dotted] (A) -- (2);
        \draw[dotted] (B) -- (3);
        \draw (C) -- (4);

        \draw[color=red, line width=12pt, cap=round, opacity=0.1] (A) -- (B);
    \end{tikzpicture}
\caption{All forests in $\forests_2(G;S)$, with floating component highlighted red. The outdegree $\degout(F(*))$ is either $2$, $3$, or $4$.}
\label{fig:2-forests}
\end{figure}

\begin{eg}\label{eg:submatrix}
    If $G$ is the tree in \Cref{fig:tree-1}, and $S = \{v_4, v_5, v_6, v_7\}$ is the set of leaf vertices,
    then the corresponding distance submatrix 
    % $D[S]$, which records pairwise distances within $S$, 
    is
    \begin{equation}\label{eq:d-submatrix-ex}
        D[S] = \begin{pmatrix}
            0 & 2 & 3 & 4 \\
            2 & 0 & 3 & 4 \\
            3 & 3 & 0 & 3 \\
            4 & 4 & 3 & 0
        \end{pmatrix}.
    \end{equation}
    In this case, the submatrix has determinant $\det D[S] = - 252$.

    The tree $G$ has $6$ edges and $13$ $S$-rooted spanning forests. 
    There are $14$ $(S, *)$-rooted spanning forests;
    of the floating components in these forests, $5$ have outdegree two, $7$ have outdegree three, and $2$ have outdegree four. 
    See Figures~\ref{fig:1-forests} and \ref{fig:2-forests}.
    One checks that
    \[
        \det D[S] = -252 = (-1)^3 2^2 \left( 6 \cdot 13 - (5 \cdot 0^1 + 7 \cdot 1^2 + 2 \cdot 2^2)\right),
    \]
    in agreement with \Cref{thm:main}.
\end{eg}

We omit the full proof of \Cref{thm:main} in this extended abstract, deferring it to our paper~\cite{richman-shokrieh-wu-3},
but provide the main steps of the argument in \Cref{sec:proof-sketch}.
In \Cref{sec:cofactor} we mention some subsequent results related to \Cref{thm:main}.

\begin{rmk}
    When $S = V$ is the full vertex set, the set of $V$-rooted spanning forests is a singleton, consisting of the subgraph with no edges, 
    so $\treecount(G; V) = 1$; and moreover the set $\forests_2(G; V)$ 
    % of $(V, *)$-rooted spanning forests 
    is empty. 
    Thus \eqref{eq:main} recovers the Graham--Pollak identity \eqref{eq:full-det} when $S = V$.
\end{rmk}

\begin{rmk}
    It is worth observing that depending on the chosen subset $S \subset V$, the distances appearing in the submatrix $D[S]$ may ignore a large part of the ambient tree $G$.
    % We could instead replace $G$ by the subtree  $\conv(S,G)$ consisting of the union of all paths between vertices in $S$, which we call the {\em convex hull} of $S \subset G$.
    To apply formula \eqref{eq:main} % or \eqref{eq:w-main} 
    ``efficiently,''
    we could replace $G$ on the right-hand side with the subtree $\conv(S,G)$ consisting of all edges on paths between vertices in $S$.
    However, the formulas as stated are true even without this replacement due to cancellation of terms.
\end{rmk}

\subsection{Cofactor sums}\label{sec:cofactor}

In~\cite{bapat-sivasubramanian}, Bapat and Sivasubramanian answered ``yes'' to a slight modification of Question~\ref{ques:3} on trees, without using determinants.
% Specifically, 
They showed that the {\em sum of cofactors} of a distance submatrix $D[S]$ of a tree
satisfies the following identity \cite[Theorem 9]{bapat-sivasubramanian}: 
% holds for 
% \footnote{See~\cite[Theorem 9]{bapat-sivasubramanian}, which combines their Theorem 8 and the all-minors matrix tree theorem of Chaiken~\cite{chaiken}},
\begin{equation}\label{eq:cof-trees}
	\cof D[S] = (-2)^{|S| - 1} \treecount(G;S) .
\end{equation}
Recall that $\treecount(G; S)$ is the number of $S$-rooted spanning forests of $G$.
Given a matrix $A$, the {sum of cofactors} of $A$ is defined as
\[
	\cof A = \sum_{i = 1}^{|S|} \sum_{j = 1}^{|S|} (-1)^{i + j} \det A_{i,j} 
\]
where $A_{i,j}$ is the submatrix of $A$ that removes the $i$-th row and the $j$-th column.
If $A$ is invertible, then $\cof A$ is 
%related to 
the sum of entries of the matrix inverse $A^{-1}$ multiplied by a factor of $\det A$, i.e. $\cof A = (\det A) (\bone^\tr A^{-1} \bone)$.
Here $\bone$ denotes the all-ones vector.

Using the Bapat--Sivasubramanian identity \eqref{eq:cof-trees}, 
\Cref{thm:main} immediately yields:
%an immediate corollary to \Cref{thm:main} is the following result:
\begin{equation}
\label{eq:det-cof}
	\frac{\det D[S]}{\cof D[S]} = \frac12 \left( (n - 1) - \frac{\sum_{F \in \forests_2(G; S)} (\degout(F,*) - 2)^2}{\treecount(G; S)} \right).
\end{equation}
Surprisingly, the expression \eqref{eq:det-cof} satisfies a monotonicity condition as we fix a tree $G$ and vary the vertex subset ${S \subset V(G)}$.

\begin{thm}[Monotonicity of ``normalized'' principal minors, {\cite[Theorem C]{richman-shokrieh-wu-3}}]
\label{thm:monotonic}
\hfill

\noindent If $A, B \subset V(G)$
are nonempty vertex subsets with
$A \subset B$,
then
\begin{equation*}
	\frac{\det D[A]}{\cof D[A]}  \leq \frac{\det D[B]}{\cof D[B]}.
\end{equation*}
\end{thm}
The monotonicity result implies the following bounds as a corollary.
\begin{thm}[Bounds on ``normalized'' principal minors, {\cite[Theorem D]{richman-shokrieh-wu-3}}]
    \label{thm:det-cof-bounds}
    Suppose $G$ is a tree with distance matrix $D$.
    \begin{enumerate}[label=(\alph*)]
    \item 
    If $\conv(S,G)$ denotes the subtree of $G$ consisting of all edges on paths between vertices of $S \subset V(G)$, then
    $\displaystyle
     \frac{\det D[S]}{\cof D[S]} \leq \frac12 |E(\conv(S, G))| .
    $
    
    \item \label{thm:det-cof-bounds-partb}
    If $\gamma$ is a simple path between vertices $s_0, s_1 \in S$, then
    $\displaystyle
        \frac12 |E(\gamma)|\leq \frac{\det D[S]}{\cof D[S]}.
    $
    \end{enumerate}
\end{thm}
We note that \Cref{thm:det-cof-bounds} \ref{thm:det-cof-bounds-partb} is an equality if $S$ consists of exactly two points.
The result in \Cref{thm:monotonic} was also independently obtained by Devriendt~\cite[Property 3.38]{devriendt} in a more general context studying effective resistance on graphs.

% Suppose we fix a tree distance matrix $D$.
% It is also natural to ask, how do the expressions $\det D[S]$ vary as we vary the vertex subset $S$? 
% To our knowledge there is no nice behavior among these determinants,
% if we do not involve cofactor sums.


\subsection{Related work}

The initial work of Graham and Pollack~\cite{graham-pollak} inspired a large amount of subsequent research on distance matrices and generalizations.
% Graham and Lov\'{a}sz~\cite{graham-lovasz} found formulas for the characteristic polynomial of the distance matrix of trees.
In~\cite{graham-hoffman-hosoya}, it is observed that the distance matrix ratio $\det D / \cof D$ is additive over wedge sums of graphs.
% Other proofs of the Graham--Pollack result \eqref{eq:full-det} are found in Yan--Yeh~\cite{yan-yeh} and Du--Yeh~\cite{du-yeh}.
Bapat, Lal, and Pati~\cite{bapat-lal-pati} defined a $q$-analogue of the distance matrix
% \footnote{The $q$-distance submatrix for \Cref{eg:submatrix} is 
% $D_q[S] = \frac1{(1 - q)^4} \begin{pmatrix}
%     % 0 & 1 + q & 1 + q + q^2 & 1 + q + q^2 + q^3 \\ 
%     % 1 + q & 0 & 1 + q + q^2 & 1 + q + q^2 + q^3 \\ 
%     % 1 + q + q^2 & 1 + q + q^2 & 0 & 1 + q + q^2 \\
%     % 1 + q + q^2 + q^3 & 1 + q + q^2 + q^3 & 1 + q + q^2 & 0
%     0 & 1 - q^2 & 1 - q^3 & 1 - q^4 \\ 
%     1 - q^2 & 0 & 1 - q^3 & 1 - q^4 \\ 
%     1 - q^3 & 1 - q^3 & 0 & 1 - q^3 \\
%     1 - q^4 & 1 - q^4 & 1 - q^3 & 0
% \end{pmatrix}$
% which has determinant $-(1 + q)^2(1 + q + q^2)^2(3 + 4q^2)$} 
and found formulas for its determinant and inverse.
Bapat~\cite{bapat-resmatrix} also found a formula for the determinant of the effective resistance matrix of a graph, although the combinatorial content here is more obscured.
It would be worth studying whether these results can be extended to arbitrary principal minors.% of these matrices. 

Choudhury and Khare~\cite{choudhury-khare} generalize the Graham--Pollak identity to some principal minors $\det D[S]$ for a certain restricted class of vertex subsets $S$.
They do so using a framework that encompasses the  $q$-analogue distance matrix as well.
% Devriendt~\cite{devriendt} studied distance matrices of trees in the more general context of effective resistance distance on graphs.
Very recently, Guti\'{e}rrez and Lillo~\cite{gutierrez-lillo} observe that \Cref{thm:main} can be expressed as
\begin{align*}
    \det D[S] & = (-1)^{|S| - 1} 2^{|S| - 2} \Big( (|S| - 1)\, \treecount(G;S) \\
	& \quad - \sum_{F \in \forests_2(G;S)} \left(\degout(F,*) - 1\right)\left(\degout(F,*) - 4\right)  \Big)
\end{align*}
through some straightforward algebraic manipulation,
while also providing a new proof for this result using a nice combinatorial argument involving sign-reversing involutions on collections of paths in $G$.

% Bapat and Sivasubramanian~\cite{bapat-sivasubramanian}

% Bapat, Lal, and Pati~\cite{bapat-lal-pati-2} also studied the minors of the adjacency matrix of a graph.


% \subsection{Terminology}\label{sec:forest-terminology}

% Given a connected subgraph $H \subset G$,
% we define the {\em edge boundary}  $\partial H$ as the set of edges which join $H$ to its complement; i.e.
% \begin{equation}
% 	\partial H = \{ e = \{a,b\} \in E : a \in V(H),\, b \not\in V(H)\}.
% \end{equation}
% We define the {\em outdegree} of $H$ as the number of edges in its edge boundary, $\degout(H) = |\partial H|$. 
% (The edge boundary and outdegree do not depend on an edge orientation.)

\section{Proof roadmap}\label{sec:proof-sketch}

Here we give a brief outline to how we obtain the expression of $\det D[S]$ that appears in \Cref{thm:main}, our main result.
The argument consists of four steps.
(Recall that $\bone$ denotes the all-ones vector.)

\begin{enumerate}[label=(\Roman*)]
\item\label{it:road-1} 
Find a vector $\boldm \in \RR^S$ such that $D[S] \boldm = \lambda \bone$, for some scalar $\lambda$.
Find $\lambda$.

\item\label{it:road-2} 
Compute $\bone^\tr \boldm$.
Since $D[S]$ is nonsingular (cf. \Cref{lem:dist-signature}), we have $\boldm = \lambda (D[S]^{-1} \bone)$ and hence
\[
    \bone^\tr \boldm = \lambda (\bone^\tr D[S]^{-1} \bone) = \lambda \cdot \frac{\cof D[S]}{\det D[S]}.
\]

\item\label{it:road-3} 
Solve or simplify $\displaystyle \frac{\det D[S]}{\cof D[S]} = \frac{\lambda}{\bone^\tr \boldm}$.

\item\label{it:road-4} 
Multiply previous expression by $\cof D[S]$, using \eqref{eq:cof-trees}, to get $\det D[S]$.
\end{enumerate}


% We can thus compute $\det D[S]$ via the following steps.
% %Given a  subset $S \subset V$ and distance submatrix $D[S]$, we will complete the following steps.
% \begin{enumerate}[label=(\roman*)]
% \item 
% Find a vector $\boldm \in \RR^S$ such that $D[S]\boldm = \lambda \mathbf{1} \in \RR^S$.

% \item 
% Compute the sum of entries of $\boldm$, i.e. $\mathbf{1}^\tr \boldm$, and normalize
% $\displaystyle
% 	\boldu^* = \frac{\boldm}{\bone^\tr \boldm}.
% $
% This solves the optimization problem of \Cref{sec:optimization}.

% \item 
% Find the optimal objective value
% % $(\boldu^*)^\tr D[S] \boldu^* = \lambda^* $
% % is
% $\displaystyle
% 	\lambda^* = \frac{\lambda}{\bone^\tr \boldm}.
% $

% \item
% Use the expression for $\cof D[S]$ in \eqref{eq:cof-trees} to compute $\det D[S] = \lambda^* (\cof D[S])$.
% % $ = \lambda (\cof D[S]) \left( \mathbf{1}^\tr \boldm \right)^{-1}.$
% \end{enumerate}
We demonstrate the steps of this proof roadmap on our running example.

\begin{eg}
Suppose $G$ is the tree from \Cref{fig:tree-1}, which we reproduce in \Cref{fig:tree-1-again}.
As before, let $S$ consist of the four leaf vertices, which are marked with larger circles.
\begin{figure}[ht]
\centering
\begin{tikzpicture}[scale=0.8]
    \coordinate (1) at (-0.5,-1);
    \coordinate (2) at (0.5,-1);
    \coordinate (3) at (2,-1);
    \coordinate (4) at (3.5,-1);
    \coordinate (A) at (0,0);
    \coordinate (B) at (1.5,0);
    \coordinate (C) at (3,0);

    \draw (1) -- (A) -- (B) -- (C) -- (4);
    \draw (A) -- (2);
    \draw (3) -- (B);

    \foreach \c in {1,2,3,4,A,B,C} {
		\fill (\c) circle (2pt);
	}
	\foreach \c in {1,2,3,4} {
		\draw (\c) circle (3pt);
	}

	\foreach \c/\dir/\label in {1/left/v_4, 2/right/v_5, 3/right/v_6, 4/right/v_7} {
		\node[\dir] at (\c) {$\label$};
	}
\end{tikzpicture}
\caption{A tree with six edges, and $S \subset V$ containing four vertices.}
\label{fig:tree-1-again}
\end{figure}

% If $S$ is the set of leaf vertices, 
The distance submatrix is 
$
D[S] = \begin{pmatrix}
    0 & 2 & 3 & 4 \\
    2 & 0 & 3 & 4 \\
    3 & 3 & 0 & 3 \\
    4 & 4 & 3 & 0
\end{pmatrix}.
$
We now compute $\det D[S]$ via the above roadmap.
\begin{enumerate}[label=(\roman*)]
\item[\ref{it:road-1}]
The vector $\boldm = \begin{pmatrix} 6 & 6 & 5 & 9 \end{pmatrix}^\tr$
satisfies $D[S] \boldm = \lambda \bone$ for $\lambda = 63$.

\item[\ref{it:road-2}] 
We have $\bone^\tr \boldm = 26$.

\item[\ref{it:road-3}]
Thus $\displaystyle \frac{\det D[S]}{\cof D[S]} = \frac{\lambda}{\bone^\tr \boldm} = \frac{63}{26}$.

\item[\ref{it:road-4}] 
Using \eqref{eq:cof-trees}, the cofactor sum is $\cof D[S] = -104$, so 
\[
    \det[S] = (\cof D[S]) \cdot \left(\frac{\det D[S]}{\cof D[S]}\right) = -252. \qedhere
\]
\end{enumerate}
\end{eg}

While not obvious here, it turns out that the entries of $\boldm$ are combinatorially meaningful (see \Cref{dfn:m-vector}),
which also gives combinatorial meaning to
%The interesting part  of this expression will turn out to be in 
the constant $\lambda$.


\section{Potential theory}

Here we discuss step~\ref{it:road-1} of the roadmap (\Cref{sec:proof-sketch}), which involves solving $D[S] \boldm = \lambda \bone$ for some $\boldm \in \RR^S$ and real $\lambda$.
This problem can be viewed through the lens of potential theory: $\boldm$ describes the distribution of charged particles among the vertices $S$, and the entries of $D[S]$ give the (negative) potential stored from interacting charges repelling one another in the ambient space $G$, depending on their position.
If the potential $D[S]\boldm$ is non-constant, charges will move from higher-potential locations to lower-potential ones (leaving total charge conserved) in order to decrease the energy $\mathcal E(\boldm) := \boldm^\tr D[S] \boldm$.
The charges will redistribute until they settle in equilibrium, such that $D[S] \boldm$ is constant on $S$.
The aim of this section is to describe the resulting {\em equilibrium distribution} $\boldm$ (up to scaling) and {\em equilibrium energy} $\boldm^\tr D[S] \boldm$.

% Fix a tree $G = (V,E)$ and a nonempty vertex subset $S \subset V$.
We first define a vector $\boldm$ which satisfies the relation $D[S] \boldm = \lambda \bone$ for some $\lambda$.

\begin{dfn}
\label{dfn:m-vector}
    Let $\boldm = \boldm(G;S)$ denote the vector in $\RR^S$ defined by
    \begin{equation}
    \label{eq:m-vector}
    \boldm_v = \sum_{T \in \trees(G;S)} (2 - \degout(T,v))
    \qquad\text{for each }v \in S,
    \end{equation}
    where $\degout(T,v)$ is the outdegree of the $v$-component of $T$.
    % (see \Cref{sec:outdegree}, equation~\eqref{eq:outdeg-forest}).
\end{dfn}

\begin{prop}
\label{prop:m-sum}
% If $S$ is nonempty, then 
The vector $\boldm = \boldm(G; S)$ defined above
satisfies
$\displaystyle \bone^\tr \boldm = 2 \,\treecount(G; S)$.
\end{prop}

% \begin{proof}
% (a)
% By \Cref{lem:outdeg-sum} we can express $\degout(T, s)$ as a sum over vertices in $T(s)$,
% \[
% 	\boldm_s = \sum_{T \in \trees(G;S)}(2 - \degout (T,s))
% = \sum_{T \in \trees(G;S)} \left( \sum_{v \in T(s)}(2 - \deg(v))\right).
% \]
% Then exchange the order of summation in $\bone^\tr \boldm$,
% \begin{align}
% 	\bone^\tr \boldm = \sum_{s\in S} \boldm_s &= \sum_{s \in S} \left( \sum_{T \in \trees(G;S)} \sum_{v \in T(s)}(2 - \deg(v)) \right) \\
% 	&= \sum_{T \in \trees(G;S)} \left( \sum_{s\in S} \sum_{v \in T(s)} (2 - \deg(v)) \right) .
% \end{align}
% Observe that the inner double sum is simply a sum over $v \in V$,
% since the vertex sets of $T(s)$ for $s \in S$ form a partition of $V$ by definition of $S$-rooted spanning forest.
% Thus 
% \[
% 	\bone^\tr \boldm = \sum_{T \in \trees} \left( \sum_{v \in V} (2 - \deg(v))\right)
% 	= 2 \treecount(G; S)
% \]
% where we apply 
% %\Cref{lem:outdeg-sum} 
% equation \eqref{eq:handshake} for the last equality.
% % as $\degout(G) = 0$.

% (b) 
% If all edge weights are positive, then $w(\overline{T}) > 0$ for all $T$, and $\trees(G; S)$ is nonempty as long as $S$ is nonempty. 
% Thus part (a) implies that $\bone^\tr \boldm > 0$.
% \end{proof}

\begin{rmk}
    The vector $\boldm$ \eqref{eq:m-vector} appears in several places in the literature, with various rescalings.
    In Bapat--Sivasubramanian~\cite[Equation (20)]{bapat-sivasubramanian}, it is denoted $\tau$.
    In Devriendt~\cite{devriendt}, it is denoted $\mathbf{p}$ called the {\em resistance curvature} vector of the Kron reduction $G / S^c$;
    the corresponding $\lambda$, such that $D[S]\mathbf{p} = \lambda \bone$, is called the {\em resistance radius} (up to rescaling by a multiple of $\kappa(G; S)$).
\end{rmk}

\subsection{Main computation}

The following is the technical heart of our main result.
See \cite{richman-shokrieh-wu-3} for the proof.

\begin{thm}
\label{thm:m-distance-product}
With $\boldm = \boldm(G;S)$ defined as in \eqref{eq:m-vector},
$D[S] \boldm = \lambda \mathbf{1}$
for the constant
\begin{equation}
\label{eq:lambda}
	\lambda = (n - 1) \treecount(G; S) - \sum_{\forests_2(G;S)} (2 - \degout(F,*))^2.
\end{equation}
%where $\degout(F,w)$ is the out-degree of the $w$-component of $F$ (as a spanning forest).
\end{thm}


\begin{rmk}
    A key step in the proof of \Cref{thm:m-distance-product} uses the following ``transition structure'' which relates the $S$-rooted spanning forests $\trees(G; S)$ with $(S, *)$-rooted spanning forests $\forests_2(G; S)$,
    via the operations of edge-deletion and edge-union.
    
    Consider the ``deletion'' map
    \[
        E(G) \times \trees(G;S) \xrightarrow{\mathrm{del}} \trees(G;S) \sqcup \forests_2(G;S)
    \]
    defined by
    $\mathrm{del}(e, T) = T \setminus e$ if $e \in T$, and $\mathrm{del}(e, T) = T$ otherwise.
    % $\displaystyle
    %     (e, T) \mapsto \begin{cases}
    %     T &\text{if } e \not\in T,\\
    %     T \setminus e &\text{if } e \in T.
    %     \end{cases}
    % $
    For a given spanning forest
    $F \in \forests_2(G;S)$,
    there are exactly $\degout(F, *)$-many choices of pairs $(e, T) \in E(G) \times \trees(G;S)$ such that
    $F = T \setminus e$.
    % For a forest $F$ in $\forests_2(G;S)$, the preimage under this map has $\degout(F,*)$ elements.
    
    There is an associated ``union'' map 
    \[
        E(G) \times \forests_2(G;S) \xrightarrow{\mathrm{uni}} \trees(G;S) \sqcup \forests_2(G;S)
    \]
    defined by $\mathrm{uni}(e, F) = F \cup e$ if $e \in \partial F(*)$, and $\mathrm{uni}(e, F) = F$ otherwise.
    Here,  $\partial F(*)$ denotes the set of edges that have one end in the floating component $F(*)$, and one end outside of it.
    For a spanning forest $T \in \trees(G; S)$, 
    there are exactly $(|V| - |S|)$-many choices of pairs $(e, F) \in E(G) \times \forests_2(G; S)$ such that $T = F \cup e$
    (since $|E(T)| = |V| - |S|$ for any such spanning forest $T$). 
    %the preimage under this map has $|E(T)|$-many elements.
\end{rmk}

% \subsection{at last}

% Finally we can prove our main theorem: for any nonempty subset $S \subset V(G)$,
% \begin{equation}
% \label{eq:main-later}
% 	\det D[S] = (-1)^{|S|-1} 2^{|S|-2} \left( (n - 1) \treecount(G;S)  - \sum_{\forests_2(G;S)} (\degout(F,*) - 2)^2 \right).
% \end{equation}
% \begin{proof}[Proof of \Cref{thm:main}]
% First, suppose $|S| = 1$.
% Then $D[S]$ is the zero matrix, and we must show that the right-hand side is zero.
% Since $G$ is a tree, $\trees(G; \{v\})$ consists of the tree $G$ itself.
% Moreover, the subgraphs in $\forests_2(G; \{v\})$ are precisely the tree splits $G \setminus e$, and for each $F = G \setminus e$ we have
% $\degout(F, *) - 2 = -1$.
% This shows that the right-hand size of \eqref{eq:main-later} is zero.

% Next, suppose $|S| \geq 2$.
% \Cref{prop:distance-sub-nonsingular} states that $D[S]$ is nonsingular, so we may use the inverse matrix identity
% \begin{equation}\label{eq:cof-invsere-sum}
% 	\bone^\tr D[S]^{-1} \bone =
% 	\frac{\cof D[S]}{\det D[S]}. 
% \end{equation}
% Let $\boldm = \boldm(G; S)$ denote the vector \eqref{eq:m-vector}.
% By 
% \Cref{prop:m-sum} (a) and
% % Bapat--Sivasubramanian~\cite[Theorem X]{bapat-sivasubramanian},
% \Cref{thm:distance-sub-cof},
% \[
% 	\bone^\tr \boldm 
% 	= 2 \sum_{T \in \trees(G;S)} w(\overline{T})
% 	= \frac{\cof D[S]}{(-1)^{1 - |S|} 2^{2 - |S|} }.
% \]
% \Cref{thm:m-distance-product} states that $D[S] \boldm = \lambda \bone$
% for some constant $\lambda$,
% which is nonzero since $D[S]$ is invertible and $\boldm$ is nonzero, c.f. \Cref{prop:m-sum} (b).
% Hence
% \begin{equation}\label{eq:inverse-sum-entries}
% 	% \frac{\cof D[S]}{\det D[S]} = 
% 	\bone^\tr D[S]^{-1} \bone
% 	= \lambda^{-1} \bone^\tr \boldm
% 	= \frac{\cof D[S]}{(-1)^{|S| - 1} 2^{|S| - 1} \lambda} .
% \end{equation}
% Comparing \eqref{eq:cof-invsere-sum} with \eqref{eq:inverse-sum-entries} gives the desired result,
% $\det D[S] = (-1)^{|S| - 1} 2^{|S| - 1} \lambda$.
% \end{proof}


\section{Monotonicity via quadratic optimization}

Here we discuss another rather surprising property of the ratio $\displaystyle \frac{\det D[S]}{\cof D[S]}$, which allows us to prove \Cref{thm:monotonic}.
Throughout, we assume that $D$ is the distance matrix of a tree.
Recall that $\cof M$ denotes the sum of cofactors of a matrix $M$.

\begin{prop}
\label{prop:optimization}
% If $D[S]$ is a principal submatrix of a distance matrix indexed by $S$, then 
%any critical value of the optimization problem \note{cite above} is equal to ${\det D[S]}/{\cof D[S]}$, i.e.
We have
$\displaystyle
	\frac{\det D[S]}{\cof D[S]} = \max \{\boldu^\tr D[S] \boldu : \boldu \in \RR^S,\, \bone^\tr \boldu = 1 \}
$.
\end{prop}

\Cref{prop:optimization} is shown in two steps: first, by use of Lagrange multipliers we can show that $\frac{\det D[S]}{\cof D[S]}$ is a critical value. 
This part is straightforward.
The second step is to confirm that the critical value is indeed a maximum, by analysis of the signature of $D[S]$.


\begin{lem}[{Bapat~\cite[Lemma 8.15]{bapat-book}}]
    \label{lem:dist-signature}
    Suppose $D$ is the distance matrix of a tree with $n$ vertices. 
    Then $D$ has one positive eigenvalue and $n - 1$ negative eigenvalues.
\end{lem}
    
Starting from \Cref{lem:dist-signature}, it is straightforward to argue that the submatrix $D[S]$ has signature $(1, |S| - 1)$; see \cite[Lemma 3.4]{richman-shokrieh-wu-3}.


% \subsection{Monotonicity}

\Cref{prop:optimization} is essentially enough for us to prove our result on the monotonicity of the ratios $\frac{\det D[S]}{\cof D[S]}$,
% behaves monotonically in 
as $S$ varies over vertex subsets of a fixed tree.

We first give a minor restatement of \Cref{prop:optimization}, viewing $\RR^S$ as a subspace of $\RR^V$ 
where coordinates indexed by $V \setminus S$ are set to zero.
\begin{cor}
\label{cor:optimization}
% If $D[S]$ is a principal submatrix of a distance matrix indexed by $S$, then 
We have
$\displaystyle
	\frac{\det D[S]}{\cof D[S]} = \max \{\boldu^\tr D \boldu : \boldu \in \RR^V,\, \bone^\tr \boldu = 1,\, \boldu_v = 0 \text{ if } v \not\in S \}
$.
% where $\cof D[S]$ denotes the sum of cofactors of $D[S]$.
\end{cor}

We now return to \Cref{thm:monotonic}.

\begin{proof}[Proof of \Cref{thm:monotonic}]
We are to show that for vertex subsets $A \subset B$, we have
$\displaystyle 
\frac{\det D[A]}{\cof D[A]} \leq \frac{\det D[B]}{\cof D[B]}.
$
By \Cref{cor:optimization}, both values $\display \frac{\det D[A]}{\cof D[A]}$ and $\display \frac{\det D[B]}{\cof D[B]}$ arise from optimizing the same objective function on an affine subspace of $\RR^V$, 
but the subspace for $A$ is contained in the subspace for $B$.
\end{proof}

% It is straightfowrad to deduce further bounds on $\displaystyle \frac{\det D[S]}{\cof D[S]}$.



\section{Extensions and applications}
\subsection{Weighted graphs}

If a tree $G = (V, E)$ is assigned positive real edge weights $\{\alpha_e : e \in E\}$,
then the weighted path distance $d^{(\alpha)}(u, v)$ is defined as the sum of the weights of edges on the unique path from $u$ to $v$.
Bapat--Kirkland--Neumann~\cite{bapat-kirkland-neumann}
proved an analogue of \eqref{eq:full-det} for the weighted distance matrix of a tree, 
\begin{equation}\label{eq:w-full-det}
	\det D = (-1)^{n-1} 2^{n-2} \sum_{e \in E} \alpha_e \prod_{e \in E} \alpha_e .
\end{equation}
We additionally have the following weighted version of our main result,
which reduces to \Cref{thm:main} when taking all unit weights, $\alpha_e = 1$.
We defer the proof to the paper~\cite{richman-shokrieh-wu-3}.

\begin{thm}
\label{thm:w-main}
Suppose $G = (V,E)$ is a tree with distance matrix $D$. 
For any nonempty subset $S \subset V$, we have
\begin{equation}\label{eq:w-main}
	\det D[S] = (-1)^{|S|-1} 2^{|S|-2} \left( \sum_{E(G)}\alpha_e \sum_{\trees(G;S)} w(\overline{T}) - \sum_{\forests_2(G;S)} w(\overline{F})\, (\degout(F,*) - 2)^2 \right),
\end{equation}
where 
$\trees(G;S)$ is the set of $S$-rooted spanning forests $T$ of $G$,
$\forests_2(G;S)$ is the set of $(S,*)$-rooted spanning forests $F$ of $G$,
$w(\overline{T})$ and $w(\overline{F})$ denote the co-weights of $T$ and $F$,
and 
$\degout(F, *)$ is the outdegree of the floating component of $F$, as above.
\end{thm}


\subsection{Symanzik polynomials}

The identity in \Cref{thm:w-main} relates closely to Symanzik polynomials, which are used in quantum field theory for studying Feynman diagrams.
We recall the definition here.
Given a graph $G = (V, E)$, the {\em first Symanzik polynomial} is the homogeneous polynomial in edge-indexed variables $\underline{x} = \{x_e : e \in E\}$ defined by
\[
	\psi_G(\underline{x}) = \sum_{T \in \trees(G)} \prod_{e \not \in T} x_e ,
\]
where $\trees(G)$ denotes the set of spanning trees of $G$.

Consider a ``momentum'' function $p: V \to \RR$ with the constraint $\sum_{v \in V} p(v) = 0$.
Then the second Symanzik polynomial is
\[
	\varphi_G(p; \underline{x}) = \sum_{F \in \forests_2(G)} \Big(\sum_{v \in F_1} p(v) \Big)^2 \prod_{e \not\in F} x_e ,
\]
where $\forests_2(G)$ is the set of two-component spanning forests of $G$, and $F_1$ denotes one of the components\footnote{
It doesn't matter which component we label as $F_1$, since the momemtum constraint implies that
$\sum_{v \in F_1} p(v) = - \sum_{v \in F_2} p(v)$.}
of $F$.

In terms of Symanzik polynomials, let $\psi$ and $\varphi$ denote the first and second Symanzik polynomials of the quotient graph $G/S$
(i.e., the graph with the same edge set as $G$, but all vertices in $S$ are glued together to a single vertex).
Let $p_{can}$ be the momentum function $p_{can}(v) = \deg(v) - 2$ for $v \not \in S$.
We have
%Then, \Cref{thm:w-main} is equivalent to the equation
\begin{equation}
\label{eq:det-symanzik}
	\det D[S] = (-1)^{|S|-1} 2^{|S|-2} \left( \Big(\sum_{E(G)}\alpha_e \Big)\, \psi_{(G/S)}(\underline{\alpha}) - \phi_{(G/S)}(p_{can}; \underline{\alpha}) \right)
\end{equation}
(equivalent to \Cref{thm:w-main}),
or more succinctly,
\begin{equation}
\label{eq:det-cof-symanzik}
	\frac{\det D[S]}{\cof D[S]} = \frac12 \left( \sum_{e \in E} \alpha_e - \frac{\varphi_{(G/S)}(p_{can}; \underline{\alpha})}{\psi_{(G/S)}(\underline{\alpha})} \right)
\end{equation}
(equivalent to a weighted version of equation~\eqref{eq:det-cof}).

\subsection{Phylogenetics}


\Cref{thm:det-cof-bounds} may be of interest to those studying phylogenetics.
In phylogenetics, one aims to find the tree that best represents the evolutionary history among a collection of organisms using biological data (e.g. DNA sequences).
In this tree, leaf vertices represent modern-day species, while internal vertices represent ancestral species.
There are standard methods for estimating pairwise distances between species along their evolutionary tree. 
This means we can often predict the distance submatrix $D[S]$ of the target tree, in which $S$ is the set of leaf vertices, and we would like to use this information in reverse to decide what underlying tree best fits this distance data.
% \farbod{Harry: did you want to say something about phylogenetic stuff?}
Results such as \Cref{thm:monotonic} may lead to new tests for phylogenetic inference, or for evaluating tree instability~\cite{collienne-etal}.


\subsection{Characteristic polynomial coefficients}

In~\cite{graham-lovasz}, Graham and Lovasz study
the characteristic polynomial 
of the distance matrix of a tree
$
    \det(D - \lambda I) = \sum_{k \geq 0} \delta_k\, \lambda^k
$.
Note that $\delta_0 = \det D$.
They generalize the determinant formula \eqref{eq:full-det} by finding a combinatorial formula for every coefficient $\delta_k = \delta_k(G)$ of the characteristic polynomial.
Their expression for $\delta_k$ involves summing over all spanning forests of $G$ with $(k - 1)$-, $k$-, or $(k + 1)$-many edges.

The simplest case of their theorem, beyond $\delta_0$, is~\cite[Equation (6), p. 63]{graham-lovasz}
\begin{equation}
    \delta_1(G) = (-1)^{n - 1} 2^{n - 3} \left(4\cdot N_{2 P_1}(G) + 2\cdot N_{P_2}(G) + 4n - 8 \right)
\end{equation}
where $G$ is a tree on $n$ vertices, and $N_{2 P_1}(G)$ (resp. $N_{P_2}(G)$) denotes the number of subgraphs of $G$ isomorphic to two disjoint edges (resp. to a two-edge path).

There is a well-known relationship between coefficients of the characteristic polynomial and principal minors, namely
\begin{equation}\label{eq:sum-of-minors}
    \delta_k = (-1)^k \sum_{\substack{|S| = n - k}} \det D[S].
\end{equation}
By applying \Cref{thm:main} and summing over vertex subsets of fixed size,
we immediately obtain another combinatorial expression for $\delta_k$.
Interestingly, this expression for $\delta_k$ looks rather different from~\cite[Equation (42), p. 81]{graham-lovasz} by Graham and Lovasz, as it involves summing over spanning forests of $G$ with $(n - k)$- or $(n - k + 1)$-many components.

It may be possible to give an alternative proof of the Graham--Lovasz identities using \Cref{thm:main}, which we leave for future work.
For now we only elaborate on the $k = 1$ case:
if $S = V \setminus \{v\}$ contains $n - 1$ vertices, then
\[
    \treecount(G; S) = \deg(v), \qquad % \text{and}\qquad
    \forestcount_2(G; S) = 1, \quad\text{and}\quad
    \degout(F, *) = \deg(v)
\]
for the unique forest $F \in \forests_2(G; S)$.
Summing over all vertex subsets with $|S| = n - 1$, we obtain
by \eqref{eq:sum-of-minors} and \eqref{eq:main} that
\begin{equation}
    \delta_1(G) = (-1)^{n - 1} 2^{n - 3} \left( (n - 1) \sum_{v \in V} \deg(v) - \sum_{v \in V} (\deg(v) - 2)^2 \right),
\end{equation}
which further simplifies to $\delta_1(G) = (-1)^{n - 1} 2^{n - 3} \left( 2(n - 1)^2 - \sum_{v \in V} (\deg(v) - 2)^2 \right)$.

% \todo{fill in}

\acknowledgements{
	The authors would like to thank Ravindra Bapat for helpful discussion, in particular for providing a pointer to \Cref{lem:dist-signature}.
	We thank Erick Matsen and the members of his lab for helpful feedback on this work.
    We also thank Matt Baker, Karel Devriendt, Apoorva Khare, and Sebastian Prillo for helpful discussions.
    We thank \'{A}lvaro Guti\'{e}rrez for helpful discussions regarding his follow-up to our work.
    We thank the anonymous reviewers for feedback that improved the exposition in numerous places. % \todo{modify?}
}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
