# Elastic Graphs

Dylan P. Thurston  Department of Mathematics
Indiana University, Bloomington, Indiana 47405
USA<EMAIL_ADDRESS>
(Date: December 13, 2016)

###### Abstract.

An _elastic graph_ is a graph with an elasticity associated to each edge. It
may be viewed as a network made out of ideal rubber bands. If the rubber bands
are stretched on a target space there is an _elastic energy_. We characterize
when a homotopy class of maps from one elastic graph to another is _loosening_
, i.e., decreases this elastic energy for all possible targets. This fits into
a more general framework of energies for maps between graphs.

###### 2010 Mathematics Subject Classification:

Primary 37E25; Secondary 58E20, 05C21

###### Contents

  1. 1 Introduction
  2. 2 Basic notions and sub-multiplicativity
  3. 3 Reduced and taut maps
  4. 4 Weak graphs and Lipschitz energy
  5. 5 Harmonic maps
  6. 6 Minimizing embedding energy
  7. A General graph energies
  8. B Relation to resistor networks

##  1\. Introduction

######  Question 1.1.

When is one network of rubber bands looser than another?

To make Question 1.1 precise, we give some definitions.

######  Definition 1.2.

In this paper, a _graph_ is a topologist’s graph, a finite 1-dimensional CW
complex, with multiple edges and self-loops allowed. _Maps_ between graphs are
continuous maps between the underlying topological spaces. In particular, they
need not send vertices to vertices. For convenience, we will work with maps
that are PL with respect to a (fixed) linear structure on each edge.

A _marked graph_ is a pair $(\Gamma,M)$, where $\Gamma$ is a graph and
$M\subset\operatorname{Vert}(\Gamma)$ is a finite subset of marked points
(possibly empty). A map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu(\Gamma_{1},M_{1})\to(\Gamma_{2},M_{2})$ between marked graphs is
required to send marked points to marked points (i.e., $f(M_{1})\subset
M_{2}$). Homotopy is considered within the space of such maps. In particular,
within a homotopy class the restriction of $f$ to a map from $M_{1}$ to
$M_{2}$ is fixed.

######  Definition 1.3.

A _length graph_ $K=(\Gamma,\ell)$ is a graph in which each edge $e$ has a
positive length $\ell(e)$. This gives a metric on $\Gamma$ respecting the
linear structure on the edges. If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ is a PL map between length graphs, then $\lvert
f^{\prime}\rvert\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to\mathbb{R}_{\geq 0}$ is the absolute value of the derivative with
respect to the metrics. It is locally constant with jump discontinuities.

######  Definition 1.4.

A _elastic graph_ $G=(\Gamma,\alpha)$ is a graph $\Gamma$ in which each edge
$e$ has a positive elastic constant $\alpha(e)$. For $G$ an elastic graph, $K$
a length graph, and $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to K$ a PL map, the _Dirichlet energy_ of $f$ is

(1.5) $\displaystyle\operatorname{Dir}(f)$
$\displaystyle\coloneqq\int_{x\in\Gamma}\lvert f^{\prime}(x)\rvert^{2}\,dx.$
(To take the derivative, we view $\alpha(e)$ as the length of the edge.) The
Dirichlet energy of a (marked) homotopy class $[f]$ is defined to be (1.6)
$\displaystyle\operatorname{Dir}[f]$
$\displaystyle\coloneqq\inf_{g\in[f]}\operatorname{Dir}(g).$

It is easy to see that a minimizer $g$ for $\operatorname{Dir}[f]$ must be
_constant-derivative_ : $\lvert g^{\prime}\rvert$ is constant on each edge of
$g$ (Definition 4.5). If $g$ is constant-derivative, we then have

(1.7)
$\operatorname{Dir}(g)=\sum_{e\in\operatorname{Edge}(\Gamma)}\frac{\ell(g(e))^{2}}{\alpha(e)},$

where $\ell(g(e))$ is the length of the image of $e$ in a natural sense
(Definition 2.2). This is the Hooke’s law energy of $g$, where each edge is an
ideal spring with resting length $0$ and spring constant given by $\alpha$.
Physically, you could think about stretching a rubber band graph shaped like
$G$ over a system of pipes shaped like $K$.

_Harmonic_ maps are maps that locally minimize the energy (1.5) or (1.7)
within their homotopy class.

Figure 1. Local schematic pictures of the equilibrium condition for harmonic
maps. Top: A vertex maps to an edge. Bottom: A vertex maps to a vertex.

Intuitively, a map is harmonic if it is constant-derivative and each vertex is
at equilibrium, in the sense that the force pulling in one direction is less
than or equal to the total force pulling it in other directions. Physically,
the force pulling a vertex in the direction of an incident edge $e$ is given
by the derivative of Equation (1.7) with respect to $\ell(g(e))$, i.e.,
$2\ell(g(e))/\alpha(e)=2\lvert f^{\prime}(e)\rvert$. We will drop the
irrelevant factor of $2$ and refer to $\lvert f^{\prime}(e)\rvert$ as the
_tension_ in the edge.

For instance, if a vertex $v$ of $G$ maps to the middle of an edge of $K$ with
three edges on the left and one edge on the right as on top of Figure 1, the
net force to the left must equal the net force to the right:

$\lvert f^{\prime}(a)\rvert+\lvert f^{\prime}(b)\rvert+\lvert
f^{\prime}(c)\rvert=\lvert f^{\prime}(d)\rvert.$

On the other hand, if a vertex $v$ of $G$ maps to a vertex $w$ of $K$ as on
the bottom of Figure 1, we no longer have an equality. Instead, the net force
pulling $v$ into any one of the three edges incident to $w$ can’t be greater
than the total force pulling it into the other two edges. This gives three
triangle inequalities:

$\displaystyle\lvert f^{\prime}(a)\rvert+\lvert f^{\prime}(b)\rvert$
$\displaystyle\leq\lvert f^{\prime}(c)\rvert+\lvert f^{\prime}(d)\rvert$
$\displaystyle\lvert f^{\prime}(c)\rvert$ $\displaystyle\leq\lvert
f^{\prime}(a)\rvert+\lvert f^{\prime}(b)\rvert+\lvert f^{\prime}(d)\rvert$
$\displaystyle\lvert f^{\prime}(d)\rvert$ $\displaystyle\leq\lvert
f^{\prime}(a)\rvert+\lvert f^{\prime}(b)\rvert+\lvert f^{\prime}(c)\rvert.$

In any homotopy class of maps to a target length graph there is a harmonic map
(Theorem 5).

######  Example 1.8.

Consider an elastic graph $G$ and length graph $K$, both tripods with their
ends marked, with elastic weights and lengths given by

$\displaystyle G$ $\displaystyle=\vbox{\hbox{$\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{energies-107}$}}$ $\displaystyle K$
$\displaystyle=\vbox{\hbox{$\includegraphics[trim=-1.00374pt -1.00374pt
-1.00374pt -1.00374pt]{energies-1}$}},$

where $x$ varies. If $x=3$, the map $f$ minimizing Dirichlet energy takes the
vertex of $G$ to a point $1/5$ of the way along an edge:

$\vbox{\hbox{$\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{energies-103}$}}\overset{f}{\longrightarrow}\vbox{\hbox{$\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{energies-10}$}}.$

The net force pulling the vertex of $G$ upwards is $4/5$, the same as the net
force pulling it downwards. The total Dirichlet energy from Equation (1.7) is

$\operatorname{Dir}(f)=\operatorname{Dir}[f]=(4/5)^{2}+(6/5)^{2}/3+(6/5)^{2}/3=8/5.$

On the other hand, if $0<x\leq 2$, then the harmonic representative has the
central vertex of $G$ mapping to the central vertex of $K$.

We can think of Dirichlet energy as a function of the target lengths (or more
precisely the target lengths and the homotopy class). We next compare these
functions.

######  Definition 1.9.

Given a homotopy class $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ of maps between marked elastic graphs, we say that
$[\phi]$ is _weakly loosening_ if, for all marked length graphs $K$ and marked
maps $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{2}\to K$,

$\operatorname{Dir}[f\circ\phi]\leq\operatorname{Dir}[f].$

If the inequality is always strict, we say that $[\phi]$ is _strictly
loosening_. For a finer invariant, define the _Dirichlet stretch factor_ to be

(1.10)
$\operatorname{SF}_{\operatorname{Dir}}[\phi]\coloneqq\sup_{[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{2}\to K}\frac{\operatorname{Dir}[f\circ\phi]}{\operatorname{Dir}[f]},$

where the supremum runs over all marked length graphs $K$ and all marked
homotopy classes $[f]$, so that $[\phi]$ is weakly loosening iff
$\operatorname{SF}_{\operatorname{Dir}}[\phi]\leq 1$. It is less obvious, but
also true that $[\phi]$ is strictly loosening iff
$\operatorname{SF}_{\operatorname{Dir}}[\phi]<1$.

######  Definition 1.11.

For $\phi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ a PL map between marked elastic graphs, the _embedding
energy_ of $\phi$ is

(1.12) $\operatorname{Emb}(\phi)\coloneqq\operatorname*{ess\,sup}_{y\in
G_{2}}\sum_{x\in\phi^{-1}(y)}\lvert\phi^{\prime}(x)\rvert.$

We are taking the essential supremum over points $y\in G_{2}$, ignoring in
particular vertices of $G_{2}$, images of vertices of $G_{1}$, and points
where $\phi^{-1}(y)$ is infinite, all of which have measure zero. For a
homotopy class $[\phi]$, define

(1.13)
$\operatorname{Emb}[\phi]\coloneqq\inf_{\psi\in[\phi]}\operatorname{Emb}(\psi).$

######  Example 1.14.

If $G_{1}$ and $G_{2}$ are both tripods with marked ends, with elastic weights
$(1,3,3)$ and $(1,1,1)$, then the minimizer for $\operatorname{Emb}(\phi)$ is
not the map from Example 1.8, but instead sends the vertex of $G_{1}$ to a
point $2/5$ of the way along an edge of $G_{2}$, with
$\operatorname{Emb}(\phi)=3/5$:

$\vbox{\hbox{$\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{energies-104}$}}\overset{\phi}{\longrightarrow}\vbox{\hbox{$\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{energies-11}$}}.$

Our answer to Question 1.1 says that
$\operatorname{Emb}[\phi]=\operatorname{SF}_{\operatorname{Dir}}[\phi]$, and
in particular the homotopy class $[\phi]$ is weakly loosening exactly when
$\operatorname{Emb}[\phi]\leq 1$. Before stating the theorem, we give another
characterization of loosening, in terms of maps to an elastic graph $G$
(rather than maps from $G$).

######  Definition 1.15.

A _marked one-manifold_ is a (not necessarily connected) one-manifold $C$ with
boundary, where the set of marked points is equal to $\partial C$. A _marked
multi-curve_ on a marked graph $\Gamma$ is a marked one-manifold $C$ and a
marked map $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to\Gamma$. (Thus, it is a union of loops on $\Gamma$ and arcs between
marked points of $\Gamma$.) A marked multi-curve is _strictly reduced_ if it
is PL and has no backtracking: on each component of $C$, $c$ is either
constant or has a perturbation that is locally injective. In each homotopy
class of multi-curves there is an essentially unique reduced representative.
If $(C,c)$ is a marked multi-curve on $\Gamma$, then for $y\in\Gamma$, define
$n_{c}(y)$ to be the size of $c^{-1}(y)$. If $c$ is reduced and $e$ is an edge
of $\Gamma$, then $n_{c}(y)$ is constant almost everywhere on $e$, so we may
write $n_{c}(e)$.

A _marked weighted multi-curve_ is a marked multi-curve in which each
component $C_{i}$ has a positive weight $w_{i}$. For weighted multi-curves,
$n_{c}(y)$ is the weighted count of $c^{-1}(y)$.

######  Definition 1.16.

The _extremal length_ of a reduced multi-curve $c$ on an elastic graph
$G=(\Gamma,\alpha)$ is

$\operatorname{EL}[c]=\operatorname{EL}(c)\coloneqq\sum_{e\in\operatorname{Edge}(G)}\alpha(e)n_{c}(e)^{2}.$

The extremal length of a homotopy class of marked multi-curves is the extremal
length of any reduced representative.

######  Definition 1.17.

For $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ a homotopy class of maps between elastic marked graphs,
the _extremal length stretch factor_ is

(1.18)
$\operatorname{SF}_{\operatorname{EL}}[\phi]\coloneqq\sup_{c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to G_{1}}\frac{\operatorname{EL}[\phi\circ c]}{\operatorname{EL}[c]}$

where the supremum runs over all multi-curves $(C,c)$ on $G_{1}$.

We are now ready to state the main result of this paper.

######  Theorem 1.

For $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ a homotopy class of maps between marked elastic graphs,

(1.19)
$\operatorname{Emb}[\phi]=\operatorname{SF}_{\operatorname{Dir}}[\phi]=\operatorname{SF}_{\operatorname{EL}}[\phi].$

Furthermore, there is

  * •

a PL map $\psi\in[\phi]$ realizing $\operatorname{Emb}[\phi]$;

  * •

a marked length graph $K$ and a PL map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{2}\to K$ realizing $\operatorname{SF}_{\operatorname{Dir}}$, in the
sense that

$\operatorname{SF}_{\operatorname{Dir}}[\phi]=\frac{\operatorname{Dir}[f\circ\phi]}{\operatorname{Dir}[f]}=\frac{\operatorname{Dir}(f\circ\psi)}{\operatorname{Dir}(f)};$

and

  * •

a marked weighted multi-curve $(C,c)$ on $G_{1}$ realizing
$\operatorname{SF}_{\operatorname{EL}}$, in the sense that $c$ and $\psi\circ
c$ are both reduced and

$\operatorname{SF}_{\operatorname{EL}}[\phi]=\frac{\operatorname{EL}(\psi\circ
c)}{\operatorname{EL}(c)}.$

Note that $\operatorname{Emb}[\phi]$ is defined as an infimum (over the
homotopy class), while $\operatorname{SF}_{\operatorname{Dir}}[\phi]$ and
$\operatorname{SF}_{\operatorname{EL}}[\phi]$ are defined as suprema (over all
possible targets or multi-curves). As such, Equation (1.19) helps us compute
these quantities, by sandwiching the target value.

In the course of the proof in Section 6, we also give an algorithm that
produces, simultaneously, the map $\psi\in[\phi]$ minimizing
$\operatorname{Emb}$, the pair $(K,f)$ maximizing the ratio of Dirichlet
energies, and the reduced multi-curve $(C,c)$ maximizing the ratio of extremal
lengths.

######  Example 1.20.

Example 1.14 fits into the following sequence of maps realizing
$\operatorname{SF}_{\operatorname{EL}}$ and
$\operatorname{SF}_{\operatorname{Dir}}$:

$\displaystyle
C\overset{c}{\longrightarrow}G_{1}\overset{\phi}{\longrightarrow}G_{2}\overset{g}{\longrightarrow}K$
$\displaystyle\vbox{\hbox{$\includegraphics[trim=-1.00374pt -1.00374pt
-1.00374pt
-1.00374pt]{energies-4}$}}\overset{c}{\longrightarrow}\vbox{\hbox{$\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{energies-103}$}}\overset{\phi}{\longrightarrow}\vbox{\hbox{$\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt
-1.00374pt]{energies-101}$}}\overset{g}{\longrightarrow}\vbox{\hbox{$\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{energies-5}$}}$

Here $c$ is the evident curve map, $\phi$ is the map from Example 1.14, and
$g$ is the map that takes the vertex of $G_{2}$ to the vertex of $K$.
Specifically, we have

$\frac{\operatorname{EL}[\phi\circ
c]}{\operatorname{EL}[c]}=\frac{4+1+1}{4+3+3}=\operatorname{Emb}(\phi)=3/5=\frac{\operatorname{Dir}[g\circ\phi]}{\operatorname{Dir}[g]}=\frac{36/25+27/25+27/25}{4+1+1}.$

We can furthermore generalize the target spaces in Theorem 1 considerably.

######  Definition 1.21.

Let $G$ be a marked elastic graph and let $X$ be a marked length space (a
length space with a distinguished finite set of points). Let $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to X$ be a Lipschitz map. Define the Dirichlet energy of $f$ by

$\displaystyle\operatorname{Dir}(f)$ $\displaystyle\coloneqq\int_{x\in
G}\lvert f^{\prime}(x)\rvert^{2}\,dx$ where $\lvert f^{\prime}(x)\rvert$ is
the best local Lipschitz constant of $f$ in a neighborhood of $x$. For a
homotopy class of marked maps, define $\displaystyle\operatorname{Dir}[f]$
$\displaystyle\coloneqq\inf_{g\in[f]}\operatorname{Dir}(g).$

In this generality, we have no guarantee that minimizers for
$\operatorname{Dir}[\phi]$ exist. (See [KS93, EF01] for some cases where
minimizers do exist.)

######  Theorem 2.

For $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ a homotopy class of maps between marked elastic graphs,

$\operatorname{Emb}[\phi]=\sup_{[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{2}\to X}\frac{\operatorname{Dir}[f\circ\phi]}{\operatorname{Dir}[f]},$

where the supremum runs over all marked length spaces $X$ and all homotopy
classes of marked maps $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{2}\to X$ with $\operatorname{Dir}[f]>0$.

We next put Theorem 1 in a broader context of graphical energies. There is a
family of energies of maps between weighted graphs, elastic graphs, and length
graphs:

(1.22) ptWeightedgraph $W$ptElasticgraph $G$ptLengthgraph $K$

pt$\sqrt{\operatorname{EL}}$

pt$\sqrt{\operatorname{Dir}}$

$\ell$

pt$\operatorname{WR}$

pt$\sqrt{\operatorname{Emb}}$

pt$\operatorname{Lip}$

(Weighted graphs, Definition 2.3, are a mild generalization of weighted multi-
curves.) The label on an arrow gives the appropriate energy of a map between
the given types of graphs. $\operatorname{EL}(f)$, $\operatorname{Emb}(f)$ and
$\operatorname{Dir}(f)$ are as defined above, except that we take the square
root for reasons to be explained shortly, and $\operatorname{EL}$ has been
extended from multi-curves to maps from general weighted graphs in a natural
way (Equation (2.5)). We make some additional definitions.

  * •

For $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to K$ a map from a weighted graph to a length graph, $\ell(f)$ is the
weighted length of the image of $f$:

(1.23) $\ell(f)\coloneqq\int_{x\in W}w(x)\lvert f^{\prime}(x)\rvert\,dx.$

  * •

For $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ a PL map between length graphs, $\operatorname{Lip}(f)$
is the best global Lipschitz constant for $f$:

(1.24) $\operatorname{Lip}(f)\coloneqq\operatorname*{ess\,sup}_{x\in
K_{1}}\lvert f^{\prime}(x)\rvert.$

  * •

For $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW_{1}\to W_{2}$ a PL map between weighted graphs, the _weight ratio_ is
the maximum ratio of weights:

(1.25) $\operatorname{WR}(c)\coloneqq\operatorname*{ess\,sup}_{y\in
W_{2}}\frac{\sum_{x\in f^{-1}(y)}w(x)}{w(y)}.$

A key fact is that these energies are _submultiplicative_ , in the sense that
the energy of a composition of two maps is less than or equal to the product
of the energies of the two pieces. To state this uniformly, we make some
further definitions.

######  Definition 1.26.

For $p\in\\{1,2,\infty\\}$, a _$p$ -conformal graph_ $G^{p}$ is

  * •

for $p=1$, a weighted graph;

  * •

for $p=2$, an elastic graph; and

  * •

for $p=\infty$, a length graph.

Let $p,q\in\\{1,2,\infty\\}$ with $p\leq q$. If we have a $p$-conformal graph
$G_{1}$, a $q$-conformal graph $G_{2}$, and a PL map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}^{p}\to G_{2}^{q}$ between them, define $E^{p}_{q}(f)$ by

$\displaystyle E^{1}_{1}(f)$ $\displaystyle\coloneqq\operatorname{WR}(f)$
$\displaystyle E^{1}_{2}(f)$
$\displaystyle\coloneqq\sqrt{\operatorname{EL}(f)}$ $\displaystyle
E^{1}_{\infty}(f)$ $\displaystyle\coloneqq\ell(f)$ $\displaystyle
E^{2}_{2}(f)$ $\displaystyle\coloneqq\sqrt{\operatorname{Emb}(f)}$
$\displaystyle E^{2}_{\infty}(f)$
$\displaystyle\coloneqq\sqrt{\operatorname{Dir}(f)}$ $\displaystyle
E^{\infty}_{\infty}(f)$
$\displaystyle\coloneqq\operatorname{Lip}(f).\vphantom{\sqrt{f}}$

In each case, for a homotopy class $[f]$ of maps, define

$E^{p}_{q}[f]\coloneqq\inf_{g\in[f]}E^{p}_{q}(g).$

Let $p,q,r\in\\{1,2,\infty\\}$ with $p\leq q\leq r$. Suppose we have a
sequence of maps

$G_{1}^{p}\overset{f}{\longrightarrow}G_{2}^{q}\overset{g}{\longrightarrow}G_{3}^{r}$

between marked graphs of the respective conformal type. Then

(1.27) $\displaystyle E^{p}_{r}(g\circ f)$ $\displaystyle\leq
E^{p}_{q}(f)E^{q}_{r}(g)$ (1.28) $\displaystyle E^{p}_{r}[g\circ f]$
$\displaystyle\leq E^{p}_{q}[f]E^{q}_{r}[g].$

See Proposition 2.15 for a more detailed statement, spelling out the cases.

More generally, $p$-conformal graphs and energies $E^{p}_{q}$ can be defined
uniformly for real numbers $p,q$ with $1\leq p\leq q\leq\infty$. See Appendix
A.

Theorem 1 can be interpreted as saying that some cases of Equation (1.28) are
tight, as follows.

######  Definition 1.29.

Let $p,q\in\\{1,2,\infty\\}$ with $p\leq q$. If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}^{p}\to G_{2}^{q}$ is a PL map between marked graphs of the
respective conformal type and

$E^{p}_{q}(f)=E^{p}_{q}[f],$

we say that $f$ is an _energy minimizer_ (in its homotopy class).

Let $p,q,r\in\\{1,2,\infty\\}$ with $p\leq q\leq r$. If we have a sequence of
maps

$G_{1}^{p}\overset{f}{\longrightarrow}G_{2}^{q}\overset{g}{\longrightarrow}G_{3}^{r}$

of PL maps between graphs of the respective conformal type, we say that this
sequence is _tight_ if $g\circ f$ is an energy minimizer and Equation (1.27)
is sharp:

$E^{p}_{r}[g\circ f]=E^{p}_{r}(g\circ f)=E^{p}_{q}(f)E^{q}_{r}(g).$

We may similarly say that a longer sequence of maps is tight.

######  Lemma 1.30.

Let
$G_{1}^{p}\overset{f}{\longrightarrow}G_{2}^{q}\overset{g}{\longrightarrow}G_{3}^{r}$
be a sequence of maps. If the sequence is tight, then $f$ and $g$ are also
energy minimizers. Conversely, if $f$ and $g$ are energy minimizers and
$E^{p}_{r}[g\circ f]=E^{p}_{q}[f]E^{q}_{r}[g]$, then the sequence is tight.

###### Proof.

In a general sequence of maps, we have inequalities:

$\displaystyle E^{p}_{r}[g\circ f]\leq E^{p}_{r}(g\circ f)\leq
E^{p}_{q}(f)E^{q}_{r}(g)$ $\displaystyle E^{p}_{r}[g\circ f]\leq
E^{p}_{q}[f]E^{q}_{r}[g]\leq E^{p}_{q}(f)E^{q}_{r}(g).$

The two conditions in the lemma assert that the inequalities in the top line
or in the bottom line are equalities. In either case, the inequalities in the
other line must be equalities as well. ∎

In this language, Theorem 1 says that, for every homotopy class of maps
$[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ between marked elastic graphs, there is a corresponding
tight sequence

$C\overset{c}{\longrightarrow}G_{1}\overset{\psi}{\longrightarrow}G_{2}\overset{f}{\longrightarrow}K$

with $\psi\in[\phi]$, $(C,c)$ a weighted multi-curve on $G_{1}$, and $K$ a
length graph. See Proposition 6.12 for more details about the structure of
maps that minimize $\operatorname{Emb}(\psi)$.

In the course of the paper, we also prove several other tightness results.

  * •

In Section 3, we prove Theorem 3, which gives a version of the max-flow/min-
cut theorem in the context of maps between graphs. This gives a
characterization of which maps minimize $E^{1}_{p}$ (for any $p$).

  * •

In Section 4, we prove Theorem 4, which shows that for any homotopy class
$[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ of maps between marked length graphs, there is a tight
sequence

$C\overset{c}{\longrightarrow}K_{1}\overset{\psi}{\longrightarrow}K_{2}$

where $\psi\in[\phi]$. This is a theorem of White, used by Bestvina [Bes11]:
the minimal Lipschitz stretch factor between metric graphs equals the maximal
ratio by which lengths of multi-curves are changed. We also extend the graphs
we are looking at to allow _weak graphs_ , where lengths are allowed to be
zero, and prove the corresponding tightness result (Theorem 4′).

  * •

In Section 5, we prove Theorem 5, which shows that for any homotopy class
$[f]\nobreak\mskip 2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip
6.0mu plus 1.0muG\to K$ of maps from a marked elastic graph to a marked length
graph, there is a tight sequence

$C\overset{c}{\longrightarrow}G\overset{g}{\longrightarrow}K$

where $g\in[f]$. Theorem 5 also characterizes the energy minimizers for
$\operatorname{Dir}(g)$ (harmonic maps). Again, we extend the results to the
setting of weak graphs (Theorem 5′).

  * •

Section 6 has the proof of the main results, Theorems 1 and 2.

  * •

Appendix A defines a family of energies $E^{p}_{q}(f)$ for any $1\leq p\leq
q\leq\infty$ and any PL map $f$ between metric graphs. Theorem 6 gives the
most general statement: for any $1\leq p\leq q\leq\infty$ and homotopy class
of maps $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to H$ between marked graphs with the appropriate extra structure, we
can find $\psi\in[\phi]$ and a tight sequence

$C\overset{c}{\longrightarrow}G\overset{\psi}{\longrightarrow}H\overset{f}{\longrightarrow}K.$

(Only a sketch of the proof of Theorem 6 is given.)

Finally, Appendix B relates the elastic networks of this paper and the more
well-studied subject of resistor networks and electrical equivalence.

Throughout the paper, we develop the theory behind these concepts, more than
is necessary for the proof of the main Theorem 1. For instance, the theory of
taut maps in Section 3 is more general than needed for the maps that actually
arise in Section 6.

The equality
$\operatorname{Emb}[\phi]=\operatorname{SF}_{\operatorname{EL}}[\phi]$ in
Theorem 1 is particularly important for applications, in light of the
connection between extremal length on surfaces and conformal embeddings
[KPT15]. In forthcoming work, we will use this to give criteria for when one
degenerating family of surfaces conformally embeds in another. These
embeddings of (degenerating) surfaces can in turn be used to give a positive
characterization of post-critically finite rational maps among branched self-
covers of the sphere [Thu16], giving a converse to an earlier characterization
by W. Thurston [DH93].

###  1.1. Prior and related work

Harmonic maps between manifolds and singular spaces have been studied for a
long time, and there is a great deal of work on various cases [GS92, KS93,
Wol95, Pic05, inter alia]. In particular, Eells and Fuglede proved that in
every homotopy class of maps between suitable (marked) Riemannian polyhedra
there is a harmonic representative [EF01, Theorem 11.2], which is a large part
of our Theorem 5. Their theory is much more general and more delicate.

The question of when one network is “looser” than another as in Definition 1.9
appears to be new. In a related context, there has been much attention devoted
to when two resistor networks are electrically equivalent; see Appendix B for
the similarities and differences.

The definition of embedding energy in Definition 1.11 also appears to be new,
although it is in a sense dual to Jeremy Kahn’s notion of domination of
weighted arc diagrams [Kah06]. Specifically, the criteria mentioned above for
embedding degenerating families of surfaces has substantial overlap with
Kahn’s work.

Theorem 1 should be thought of as analogous to Teichmüller’s theorem, that in
any homotopy class of homeomorphism $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muS_{1}\to S_{2}$ between closed Riemann surfaces there are “best” metrics
on $S_{1}$ and $S_{2}$ that reflect the minimal quasi-conformal stretching.
(The length graph $K$ in the statement of Theorem 1 turns out to be $G_{2}$
with a different metric.) Indeed, Palmer has an approach to use these
techniques to compute Teichmüller maps [Pal15].

Most of the general graph energies in Section A appear to be new, but the
energy $E^{1}_{p}[c]$ is a power of the $p$-modulus of the homotopy class,
which exists in much greater generality [Fug57].

Many of the results of this paper were announced as part of an earlier
research report [Thu16], which also contains many related open problems.

###  1.2. Acknowledgements

This project grew out of joint work with Kevin Pilgrim, and owes a great deal
to conversations with him and with Jeremy Kahn. There were additional helpful
conversations with Maxime Fortier Bourque and Steven Gortler. This work was
partially supported by NSF grants DMS-1358638 and DMS-1507244.

##  2\. Basic notions and sub-multiplicativity

As mentioned already, all graphs are assumed to have a linear structure on the
edges, metrics are assumed to be linear with respect to this structure,
weights are assumed to be piecewise-constant, and maps between graphs are
assumed to be PL. All the energies extend naturally to a wider class of maps
between graphs; however, the exact wider class of maps depends on the energy,
and it is more convenient to stick to PL maps. The downside of working with PL
maps is that the existence of minimizers of the energies is not obvious, since
the space of PL maps is not locally compact in any reasonable sense. We will
prove existence of energy minimizers in each case of interest.

We start by defining our graphs and energies more.

######  Definition 2.1.

If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ is a PL map, the _regular points_ of $f$ are the
points in $\Gamma_{1}$ that are in the interior of a segment on which $f$ is
linear with non-zero derivative, and the _singular points_ are all other
points, namely vertices of $\Gamma_{1}$, preimages of vertices of
$\Gamma_{2}$, points where the derivative changes, and segments on which $f$
is constant. Similarly, the _singular values_ in $\Gamma_{2}$ are the images
of singular points, and the _regular values_ are the rest of $\Gamma_{2}$.
There are only finitely many singular values.

######  Definition 2.2.

As in the introduction, a length graph $K$ is a pair $(\Gamma,\ell)$ of a
graph and an assignment of a length $\ell(e)>0$ to edge $e$ of $\Gamma$; we
call $\ell$ a _metric_ on $\Gamma$. In a _weak length graph_ , we weaken the
conditions to require $\ell(e)\geq 0$. The space of all weak metrics on
$\Gamma$ is denoted $\mathcal{L}(\Gamma)$, and the subspace of metrics is
denoted $\mathcal{L}^{+}(\Gamma)$. See Definition 4.1 for more on weak
metrics. Given a PL map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to(\Gamma_{2},\ell)$ to a length graph, we can pull-back the
metric on $\Gamma_{2}$ to a weak metric $f^{*}\ell$ on $\Gamma_{1}$, assigning
to each edge $e\in\operatorname{Edge}(\Gamma_{1})$ the total length traced out
by $f(e)$. We also write $\ell(f(e))$ for $f^{*}\ell(e)$.

######  Definition 2.3.

A _weighted graph_ is a graph $W=(\Gamma,w)$ with a piecewise-constant weight
function $w\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma\to\mathbb{R}_{\geq 0}$. If $w$ is constant on an edge $e$, we
write $w(e)$ for the weight on $e$. The space of all weights on $\Gamma$ that
are constant on each edge is denoted $\mathcal{W}(\Gamma)$, and
$\mathcal{W}^{+}(\Gamma)$ is the subspace where the weights are positive.

######  Definition 2.4.

For $W$ a weighted graph, $\Gamma$ a graph, and $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ a PL map, the _multiplicity function_ $n_{c}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma\to\mathbb{R}$ is defined at regular values of $c$ by

$n_{c}(y)\coloneqq\sum_{x\in c^{-1}(y)}w(x).$

This may also be written $n_{c}^{w}$ or $c_{*}w$ if we need to make the
dependence on $w$ explicit. We will never care about the value of $n_{c}$ at
non-regular values.

If in addition $\Gamma$ has more structure we have an energy.

  * •

If $\Gamma$ is also a weighted graph with its own weights $w$, the _weight
ratio_ was defined in Equation (1.25); it is the $\ell^{\infty}$ norm of
$n_{c}$.

  * •

If $\Gamma$ is an elastic graph with elastic constants $\alpha$, the _extremal
length_ of $c$ is

(2.5) $\operatorname{EL}(c)\coloneqq\int_{y\in\Gamma}n_{c}(y)^{2}\,dy,$

where we view each edge $e$ of $G$ as having a measure of total mass
$\alpha(e)$. This generalizes Definition 1.16; $\operatorname{EL}(c)$ is the
$\ell^{2}$ norm of $n_{c}$, squared.

  * •

If $\Gamma$ is a length graph with lengths $\ell$, the _weighted length_ of
$c$ was defined in Equation (1.23); by Lemma 2.10 below, it is the $\ell^{1}$
norm of $n_{c}$.

In Section 3 we will show that each homotopy class has a _taut map_ that
simultaneously minimizes $n_{c}(y)$ for all regular values $y\in\Gamma$. Taut
maps are automatically minimizers of $\operatorname{WR}$, $\operatorname{EL}$,
and $\ell$, independent of which weight, elastic, or length structure we put
on $\Gamma$. If $c$ is taut, $n_{c}$ is constant on each edge of $\Gamma$ and
Equation (2.5) reduces to

$\displaystyle\operatorname{EL}(c)$
$\displaystyle=\sum_{e\in\operatorname{Edge}(G)}n_{c}(e)^{2}\cdot\alpha(e)$

In addition to these energies, the energies $\operatorname{Emb}$,
$\operatorname{Dir}$, and $\operatorname{Lip}$ were defined in Section 1. For
all of these energies, if we wish to make explicit the dependence of the
energy on the geometric structure, we use superscripts for the structure on
the domain and subscripts for the structure on the range. Thus we write
$\operatorname{WR}^{w_{1}}_{w_{2}}$, $\operatorname{EL}^{w}_{\alpha}$,
$\ell^{w}_{\ell}$, $\operatorname{Emb}^{\alpha_{1}}_{\alpha_{2}}$,
$\operatorname{Dir}^{\alpha}_{\ell}$, or
$\operatorname{Lip}^{\ell_{1}}_{\ell_{2}}$.

To work with these energies, we give some elementary lemmas, starting with
another formula for Dirichlet energy.

######  Definition 2.6.

For $G$ an elastic graph, $\Gamma$ either a length graph or an elastic graph,
and $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to\Gamma$ a PL map, the _filling function_
$\operatorname{Fill}_{f}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma\to\mathbb{R}$ is defined at regular values of $f$ by

(2.7) $\operatorname{Fill}_{f}(y)\coloneqq\sum_{x\in f^{-1}(y)}\lvert
f^{\prime}(x)\rvert.$

In particular, Equation (1.12) says that
$\operatorname{Emb}(f)=\operatorname*{ess\,sup}_{y}\operatorname{Fill}_{f}(y)$.

######  Lemma 2.8.

For $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to K$ a PL map from an elastic graph to a length graph,

(2.9) $\operatorname{Dir}(f)=\int_{x\in\Gamma}\lvert
f^{\prime}\rvert^{2}\,dx=\int_{y\in K}\operatorname{Fill}_{f}(y)\,dy.$

There is a corresponding formula for $\ell$.

######  Lemma 2.10.

For $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to K$ a PL map from a weighted graph to a length graph,

(2.11) $\ell(c)=\int_{x\in W}w(x)\lvert c^{\prime}(x)\rvert\,dx=\int_{y\in
K}n_{c}(y)\,dy.$

###### Proof of Lemmas 2.8 and 2.10.

Change of variables. ∎

######  Lemma 2.12.

For
$G_{1}\overset{\phi}{\longrightarrow}G_{2}\overset{\psi}{\longrightarrow}\Gamma$
a sequence of PL maps between graphs, where $G_{1}$ and $G_{2}$ are elastic
graphs and $\Gamma$ is a length graph or an elastic graph, for almost every
$z\in\Gamma$,

$\operatorname{Fill}_{\psi\circ\phi}(z)=\sum_{y\in\psi^{-1}(z)}\lvert\psi^{\prime}(y)\rvert\operatorname{Fill}_{\phi}(y)\leq\operatorname{Emb}(\phi)\,\operatorname{Fill}_{\psi}(z).$

######  Lemma 2.13.

Let
$W_{1}\overset{\phi}{\longrightarrow}W_{2}\overset{c}{\longrightarrow}\Gamma$
be a sequence of PL maps, with $W_{1}$ and $W_{2}$ weighted graphs. Then for
almost every $z\in\Gamma$,

$n_{c\circ\phi}(z)\leq\operatorname{WR}(\phi)n_{c}(z).$

######  Lemma 2.14.

Let
$\Gamma\overset{f}{\longrightarrow}K_{1}\overset{\phi}{\longrightarrow}K_{2}$
be a sequence of PL maps, with $K_{1}$ and $K_{2}$ length graphs. Then for
almost every $x\in\Gamma$,

$\bigl{\lvert}(\phi\circ f)^{\prime}(x)\bigr{\rvert}\leq\lvert
f^{\prime}(x)\rvert\operatorname{Lip}(\phi).$

###### Proof of Lemmas 2.12, 2.13, and 2.14.

Immediate from the definitions. ∎

We now turn to sub-multiplicativity, Equations (1.27) and (1.28). For
concreteness (and because the square roots get a little confusing), we list
all 10 cases individually.

######  Proposition 2.15.

The energies from (1.22) are sub-multiplicative, in the following sense. For
$i\in\\{1,2,3\\}$, let $W_{i}$ be marked weighted graphs, $G_{i}$ be marked
elastic graphs, and $K_{i}$ be marked length graphs. Then, if we are given
marked PL maps between these spaces as specified on each line, we have the
given inequality.

(2.16) $\displaystyle W_{1}\overset{\phi}{\longrightarrow}\,$ $\displaystyle
W_{2}\overset{\psi}{\longrightarrow}W_{3}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\operatorname{WR}(\psi\circ\phi)$
$\displaystyle\leq\operatorname{WR}(\phi)\operatorname{WR}(\psi)$ (2.17)
$\displaystyle W_{1}\overset{\phi}{\longrightarrow}\,$ $\displaystyle
W_{2}\overset{c}{\longrightarrow}G\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\operatorname{EL}(c\circ\phi)$
$\displaystyle\leq\operatorname{WR}(\phi)^{2}\operatorname{EL}(c)$ (2.18)
$\displaystyle W_{1}\overset{\phi}{\longrightarrow}\,$ $\displaystyle
W_{2}\overset{f}{\longrightarrow}K\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\ell(f\circ\phi)$
$\displaystyle\leq\operatorname{WR}(\phi)\ell(f)$ (2.19) $\displaystyle
W\overset{c}{\longrightarrow}\,$ $\displaystyle
G_{1}\overset{\phi}{\longrightarrow}G_{2}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\operatorname{EL}(\phi\circ c)$
$\displaystyle\leq\operatorname{EL}(c)\operatorname{Emb}(\phi)$ (2.20)
$\displaystyle W\overset{c}{\longrightarrow}\,$ $\displaystyle
G\overset{f}{\longrightarrow}K\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\ell(f\circ c)^{2}$
$\displaystyle\leq\operatorname{EL}(c)\operatorname{Dir}(f)$ (2.21)
$\displaystyle W\overset{c}{\longrightarrow}\,$ $\displaystyle
K_{1}\overset{\phi}{\longrightarrow}K_{2}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\ell(\phi\circ c)$
$\displaystyle\leq\ell(c)\operatorname{Lip}(\phi)$ (2.22) $\displaystyle
G_{1}\overset{\phi}{\longrightarrow}\,$ $\displaystyle
G_{2}\overset{\psi}{\longrightarrow}G_{3}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\operatorname{Emb}(\psi\circ\phi)$
$\displaystyle\leq\operatorname{Emb}(\phi)\operatorname{Emb}(\psi)$ (2.23)
$\displaystyle G_{1}\overset{\phi}{\longrightarrow}\,$ $\displaystyle
G_{2}\overset{f}{\longrightarrow}K\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\operatorname{Dir}(f\circ\phi)$
$\displaystyle\leq\operatorname{Emb}(\phi)\operatorname{Dir}(f)$ (2.24)
$\displaystyle G\overset{f}{\longrightarrow}\,$ $\displaystyle
K_{1}\overset{\phi}{\longrightarrow}K_{2}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\operatorname{Dir}(\phi\circ f)$
$\displaystyle\leq\operatorname{Dir}(f)\operatorname{Lip}(\phi)^{2}$ (2.25)
$\displaystyle K_{1}\overset{\phi}{\longrightarrow}\,$ $\displaystyle
K_{2}\overset{\psi}{\longrightarrow}K_{3}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus 1.0mu$
$\displaystyle\operatorname{Lip}(\psi\circ\phi)$
$\displaystyle\leq\operatorname{Lip}(\phi)\operatorname{Lip}(\psi).$

(When there is only one graph of a particular type, we omit the subscript.)
Each inequality still holds if we take homotopy classes on both sides.

###### Proof.

Equations (2.16), (2.17), and (2.18) follow from Lemma 2.13 and Equations
(1.25), (2.5), and (2.11), respectively. Equations (2.21), (2.24), and (2.25)
follow from Lemma 2.14 and Equations (2.11), (1.5), and (1.24), respectively.

For Equation (2.19), we have

$\displaystyle\operatorname{EL}(\phi\circ c)$ $\displaystyle=\int_{z\in
G_{2}}n_{\phi\circ c}(y)^{2}\,dz$ $\displaystyle=\int_{z\in
G_{2}}\biggl{(}\sum_{\phi(y)=z}n_{c}(y)\biggr{)}^{2}\,dz$
$\displaystyle\leq\int_{z\in
G_{2}}\biggl{(}\sum_{\phi(y)=z}n_{c}(y)^{2}/\lvert\phi^{\prime}(y)\rvert\biggr{)}\biggl{(}\sum_{\phi(y)=z}\lvert\phi^{\prime}(y)\rvert\biggr{)}\,dz$
$\displaystyle\leq\operatorname{Emb}(\phi)\int_{y\in G_{1}}n_{c}(y)^{2}\,dy$
$\displaystyle=\operatorname{Emb}(\phi)\operatorname{EL}(c),$

using the definition of $\operatorname{EL}$; the equality $n_{\phi\circ
c}(y)=\sum_{\phi(x)=y}n_{c}(x)$ at regular values; the Cauchy-Schwarz
inequality; the definition of $\operatorname{Emb}(\phi)$ and a change of
variables between $G_{2}$ and $G_{1}$; and the definition of
$\operatorname{EL}$ again.

For Equation (2.20), we have

$\displaystyle\ell(f\circ c)^{2}$ $\displaystyle=\left(\int_{z\in K}n_{f\circ
c}(z)\,dz\right)^{2}$ $\displaystyle=\left(\int_{y\in G}n_{c}(y)\lvert
f^{\prime}(y)\rvert\,dy\right)^{2}$ $\displaystyle\leq\left(\int_{y\in
G}n_{c}(y)^{2}\,dy\right)\left(\int_{y\in G}\lvert
f^{\prime}(y)\rvert^{2}\,dy\right)$
$\displaystyle=\operatorname{EL}(c)\operatorname{Dir}(f),$

using Lemma (2.10), a change of variables from $K$ to $G$, the Cauchy-Schwarz
inequality, and the definitions of $\operatorname{EL}$ and
$\operatorname{Dir}$.

Equation (2.22) follows from Lemma 2.12.

For Equation (2.23), we have

$\displaystyle\operatorname{Dir}(f\circ\phi)$ $\displaystyle=\int_{z\in
K}\operatorname{Fill}_{f\circ\phi}(z)\,dz$ $\displaystyle\leq\int_{z\in
K}\operatorname{Fill}_{f}(z)\Bigl{(}\max_{f(y)=z}\operatorname{Fill}_{\phi}(y)\Big{)}\,dz$
$\displaystyle\leq\int_{z\in
K}\operatorname{Fill}_{f}(z)\operatorname{Emb}(\phi)\,dz$
$\displaystyle=\operatorname{Emb}(\phi)\operatorname{Dir}(f),$

using Lemma 2.8, Lemma 2.12, the definition of $\operatorname{Emb}(\phi)$, and
Lemma 2.8 again.

For each of these equations, to replace concrete functions by homotopy
classes, take representatives $f,g$ of the two homotopy classes whose energy
is within a factor of $\varepsilon$ of the optimal value, in the sense that
$E^{p}_{q}[f]\leq E^{p}_{q}(f)\leq E^{p}_{q}[f](1+\varepsilon)$, and similarly
for $g$. Then

$E^{p}_{r}[g\circ f]\leq E^{p}_{r}(g\circ f)\leq E^{p}_{q}(f)E^{q}_{r}(g)\leq
E^{p}_{q}[f]E^{q}_{r}[g](1+\varepsilon)^{2}.$

Since $\varepsilon$ can be chosen as small as desired, we are done. ∎

We now have one direction of Theorem 1.

######  Corollary 2.26.

For any homotopy class $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ of maps between marked elastic graphs,
$\operatorname{SF}_{\operatorname{Dir}}[\phi]\leq\operatorname{Emb}[\phi]$ and
$\operatorname{SF}_{\operatorname{EL}}[\phi]\leq\operatorname{Emb}[\phi]$.

###### Proof.

For any marked length graph $K$ and homotopy class $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{2}\to K$, by the homotopy version of Equation (2.23) we have

$\frac{\operatorname{Dir}[f\circ\phi]}{\operatorname{Dir}[f]}\leq\frac{\operatorname{Dir}[f]\operatorname{Emb}[\phi]}{\operatorname{Dir}[f]}=\operatorname{Emb}[\phi].$

Since $K$ and $[f]$ were arbitrary, it follows that
$\operatorname{SF}_{\operatorname{Dir}}[\phi]\leq\operatorname{Emb}[\phi]$.
The argument that
$\operatorname{SF}_{\operatorname{EL}}[\phi]\leq\operatorname{Emb}[\phi]$ is
exactly parallel. ∎

##  3\. Reduced and taut maps

We next turn to notions of efficiency of maps between graphs. We first have a
weak notion depending on no extra structure (“reduced”), and then develop more
a notion that depends on a weight structure (“taut”).

###  3.1. Reduced maps

We work by analogy with the standard notion of a reduced (cyclic) word in a
group.

######  Definition 3.1.

A map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ between marked graphs is _edge-reduced_ if, on
each edge $e$ of $\Gamma_{1}$, $f$ is either constant or has a perturbation
that is locally injective.

######  Definition 3.2.

For a graph $\Gamma$ and point $x\in\Gamma$, a _direction_ $d$ at $x$ is a
germ of a PL map from $\mathbb{R}_{\geq 0}$ to $\Gamma$ starting at $x$,
considered up to PL reparametrization. There is always a _zero_ direction, the
germ of a constant map. Points on edges of $\Gamma$ have two non-zero
directions, and vertices have as many non-zero directions as their valence. If
$f\nobreak\mskip 2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip
6.0mu plus 1.0mu\Gamma_{1}\to\Gamma_{2}$ is a PL map and $d$ is a direction at
$x\in\Gamma_{1}$, then $f(d)$ is a direction at $f(x)$.

######  Definition 3.3.

A PL map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ between marked graphs is _strictly reduced_ if
it is locally injective on the edges of $\Gamma_{1}$ and, at each unmarked
vertex $v$ of $\Gamma_{1}$, there are directions $d_{1}$ and $d_{2}$ at $v$ so
that $f(d_{1})$ and $f(d_{2})$ are distinct and non-zero.

More generally, pick $y\in\Gamma_{2}$ and let $Z\subset\Gamma_{1}$ be a
component of $f^{-1}(y)$. A _direction_ from $Z$ is a point $x\in Z$ and a
direction $d$ from $x$ that points out of $Z$ (so that $f(d)$ is non-zero).
Then $Z$ is a _dead end_ for $f$ if $Z$ has no marked point and there is
exactly one direction in

$D(Z)\coloneqq\\{\,f(d)\mid\text{$d$ a direction from $Z$}\,\\}.$

(If $D(Z)=\emptyset$, then $Z$ is necessarily an entire connected component of
$\Gamma_{1}$. We do not count this as a dead end.) We say that $f$ is
_reduced_ if it has no dead ends. If $f$ is not reduced, there is a natural
_reduction_ operation at a dead end $Z$, where we modify $f$ by pulling the
image of $Z$ in the direction $D(Z)$ until it hits a vertex of $\Gamma_{2}$ or
the boundary of a domain of linearity.

######  Proposition 3.4.

If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ is any map between marked graphs, then repeated
reduction makes $f$ into a reduced map. In particular, there is a reduced map
in every homotopy class.

###### Proof.

Proceed by induction on the number of linear segments of $f$ with non-zero
derivative. This is reduced by each reduction operation. ∎

######  Proposition 3.5.

For $p,q\in\\{1,2,\infty\\}$ with $1\leq p\leq q\leq\infty$, reduction does
not increase $E^{p}_{q}$, and strictly decreases $E^{p}_{q}$ if $p<q$.

###### Proof.

Clear from the definitions. ∎

As a result of Propositions 3.4 and 3.5, when looking for energy minimizers we
can restrict our attention to reduced maps.

###  3.2. Taut maps and flows

We now add some more structure, and correspondingly get more restrictive
conditions on energy-minimizing maps. We will consider maps from weighted
graphs, and in particular how to minimize $E^{1}_{q}$ for any $q$.

######  Definition 3.6.

Let $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ be a PL map from a marked weighted graph $W$ to a marked
graph $\Gamma$. We defined the multiplicity $n_{c}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma\to\mathbb{R}_{\geq 0}$ in Definition 2.4. To define a multiplicity
for homotopy classes, for $y$ in the interior of an edge of $\Gamma$ set

$n_{[c]}(y)\coloneqq\inf_{d\in[c]}n_{d}(y).$

The infimum is taken over maps $d$ for which $n_{d}(y)$ is defined. Then
$n_{[c]}(y)$ depends only on the edge containing $y$. We say that $c$ is
_taut_ if $n_{c}=n_{[c]}$ almost everywhere. We say that $c$ is _locally taut_
if every regular value $y\in\Gamma$ has a regular neighborhood $N$ so that
$n_{c}$ cannot be reduced by homotopy of $c$ on $c^{-1}(N)$. (A _regular
neighborhood_ of $y$ is a tubular neighborhood of $y$ that has no singular
points except possibly at $y$. In particular, it has no other vertices of
$\Gamma$.)

It will require work to show that taut maps exist, but if they do exist they
have good properties.

######  Lemma 3.7.

A taut map from a positive weighted graph is reduced.

###### Proof.

Reduction reduces $n_{c}$. ∎

######  Proposition 3.8.

Let $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ be a taut map from a marked weighted graph $W$ to a marked
graph $\Gamma$. If $\Gamma$ is weighted, then $\operatorname{WR}(c)$ is
minimal in $[c]$. If $\Gamma$ has an elastic structure, then
$\operatorname{EL}(c)$ is minimal in $[c]$. If $\Gamma$ has a length
structure, then $\ell(c)$ is minimal in $[c]$.

###### Proof.

Clear from the definitions, since the energies are monotonic in $n_{c}$. When
$\Gamma$ is a length graph, we use Lemma 2.10. ∎

######  Example 3.9.

Let $W$ be a marked weighted graph with two marked vertices $s$ and $t$. Let
$I$ be the interval $[-1,1]$ with the endpoints marked, and let
$f\nobreak\mskip 2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip
6.0mu plus 1.0muW\to I$ be a map with $f(s)=-1$ and $f(t)=1$. Then $f$ is taut
iff each edge is mapped monotonically and, for each regular value $y\in I$,
the set of edges containing $f^{-1}(y)$ is a _minimal cut-set_ for $W$, a set
of edges of $W$ that separates $s$ from $t$ and has minimal weight among all
such sets.

The max-flow/min-cut theorem says that in the context of Example 3.9 the total
weight of a minimal cut-set for $W$ is equal to the maximum flow from $s$ to
$t$ through the edges of $t$. We will show that taut maps exist, and that they
satisfy a generalization of the max-flow/min-cut theorem; see Theorem 3 and
Corollary 3.29 below. To give the strongest statement, we make some
definitions and preliminary lemmas first.

######  Lemma 3.10.

A marked weighted multi-curve $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to\Gamma$ on a marked graph $\Gamma$, with weights that are positive
and constant on the components of $C$, is taut iff it is reduced.

###### Proof.

One direction is Lemma 3.7. For the other direction, use the standard fact
that, given a non-trivial free homotopy class of maps from $S^{1}$ to
$\Gamma$, a strictly reduced representative is unique up to reparametrization
of the domain (which does not change $n_{c}$). The same is true for homotopy
classes of maps from $I$ to $\Gamma$ relative to the endpoints. ∎

######  Definition 3.11.

If $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW_{1}\to W_{2}$ is a PL map between weight graphs, we say that $W_{2}$
_carries_ $(W_{1},c)$ if $\operatorname{WR}(c)\leq 1$. If $W_{2}$ carries
$(W_{1},c)$, then we say that a point $y$ of $W_{2}$ is _saturated_ if
$n_{c}(y)=w(y)$. Similarly, a subset of a weighted graph is saturated if
almost every point in it is saturated.

One notion of a “flow” on a weighted graph $W$ is a taut weighted multi-curve
carried by $W$. These curves are a little awkward to work with directly. As
such, we will also define and work with a more general type of flow from
_train tracks_.

######  Definition 3.12.

A sequence of non-negative numbers $(x_{i})_{i=1}^{k}$ is said to satisfy the
_triangle inequalities_ if, for each $i$, $x_{i}$ is no larger than the sum of
the remaining numbers:

(3.13) $x_{i}\leq\sum_{\begin{subarray}{c}1\leq j\leq k\\\ i\neq
j\end{subarray}}x_{j}.$

This implies that $k\neq 1$, and if $k=2$ then $x_{1}=x_{2}$. If $k\geq 3$ and
one of these inequalities is an equality, then there is exactly one $i$ so
that $x_{i}$ is equal to the sum of the remainder. That $x_{i}$ is said to
_dominate_ the rest.

######  Definition 3.14.

A _train-track structure_ $\tau$ on a graph $\Gamma$ is, for each point $x$ of
$\Gamma$, a partition of the non-zero directions from $x$ into equivalence
classes, called the _gates_ at $x$, with at least two gates at each unmarked
point.

If $\Gamma$ is weighted, the _weight_ of a gate is the sum of the weights of
the edges corresponding to the directions that make it up. A _weighted train
track_ $T$ is a tuple $(\Gamma,w,\tau)$ of a marked weighted graph
$(\Gamma,w)$ with a train-track structure $\tau$ so that, at each unmarked
vertex, the weights of the gates satisfy the triangle inequalities. (If we
don’t want to impose the triangle inequalities, we may refer to a weighted
graph with a train-track structure.) If the weight of one gate $g$ at a vertex
of a weighted train track dominates the others, we can _smooth_ the vertex,
changing the train-track structure so that there are only two gates, one with
the directions from $g$ and one with all the other directions.

A graph $\Gamma$ with no unmarked univalent ends has a _discrete_ train-track
structure $\delta_{\Gamma}$, in which two different directions are never
equivalent. By default we use the discrete train-track structure on a graph. A
weighted graph for which the discrete train-track structure satisfies the
triangle inequalities is said to be _balanced_.

If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu(\Gamma_{1},\tau_{1})\to(\Gamma_{2},\tau_{2})$ is a map between train
tracks that is locally injective on the edges of $\Gamma_{1}$, we say that $f$
is a _train-track map_ if, for each vertex $v$ of $\Gamma_{1}$ and directions
$d_{1}$ and $d_{2}$ at $v$,

(3.15)
$\bigl{(}d_{1}\sim_{\tau_{1}}d_{2}\bigr{)}\Longleftrightarrow\bigl{(}f(d_{1})\sim_{\tau_{2}}f(d_{2})\bigr{)}.$

More generally, we say that $f$ is a train-track map if it has arbitrarily
small perturbations $f_{\varepsilon}$ so that $f_{\varepsilon}$ is locally
injective on the edges of $\Gamma_{1}$ and satisfies Equation (3.15). In
particular, a curve $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to\Gamma$ is a train-track map iff at each point it passes through the
incoming and outgoing directions are in different gates.

If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ is a strictly reduced map, the _train track of
$f$_ is the unique train-track structure $\tau(f)$ on $\Gamma_{1}$ so that $f$
is a train-track map with respect to the train track structures $\tau(f)$ on
$\Gamma_{1}$ and $\delta_{\Gamma_{2}}$ on $\Gamma_{2}$. Concretely,

$\bigl{(}d_{1}\sim_{\tau(f)}d_{2}\bigr{)}\Longleftrightarrow\bigl{(}f(d_{1})=f(d_{2})\bigr{)}.$

A composition of train-track maps is a train-track map.

We can now state the main goal of this section.

######  Theorem 3.

Let $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ be a PL map from a marked weighted graph to a marked graph.
Then there is a taut map in $[f]$. Furthermore, the following conditions are
equivalent.

  1. (1)

The map $f$ is taut.

  2. (2)

The map $f$ is locally taut.

  3. (3)

The graph $W$ carries a marked weighted train track $t\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muT\to W$, so that $f\circ t$ is a train-track map (with respect to the
discrete train track structure on $\Gamma$) and $n_{f\circ t}=n_{t}$. We may
choose $(T,t)$ so that $T$ is a subgraph of $W$.

  4. (4)

The graph $W$ carries a marked weighted multi-curve $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to W$ so that $f\circ c$ is taut and $n_{f\circ c}=n_{f}$.

Furthermore, in conditions (3) and (4), $c$ and $t$, respectively, saturate
every edge of $W$ on which $f$ is not constant.

As a preliminary step towards Theorem 3, we relate train tracks and multi-
curves.

######  Proposition 3.16.

Any weighted train track $T=(\Gamma,w,\tau)$ carries a marked weighted multi-
curve $(C,c)$ that saturates $T$ and so that $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to T$ is a train-track map. We can choose $(C,c)$ so that each
component of $C$ runs over each edge of $\Gamma$ at most twice.

###### Proof.

Let $T^{\prime}\subset T$ be the sub-train-track of edges of non-zero weight.
Let $T^{\prime\prime}$ be $T^{\prime}$ modified by smoothing all vertices in
which one gate dominates the others. Let
$\mathop{\mathrm{Yard}}(T^{\prime\prime})\subset\operatorname{Vert}(T^{\prime\prime})$
be the set of marked vertices of $T^{\prime\prime}$ with at least three gates.
We will proceed by induction on
$\lvert\operatorname{Edge}(T^{\prime\prime})\rvert+\lvert\mathop{\mathrm{Yard}}(T^{\prime\prime})\rvert$.

In the base case, $T^{\prime}$ and $T^{\prime\prime}$ are empty.

Otherwise, choose any oriented edge $\vec{e}_{0}$ of $T^{\prime\prime}$, and
find a path (forward and backwards) from $\vec{e}_{0}$ within
$T^{\prime\prime}$, always making turns between different gates. Since there
are at least two gates at each marked vertex, we can always find a successor
edge for $\vec{e}_{i}$, unless we hit a marked vertex. Since there are only
finitely many oriented edges in $T$, we will eventually either find a path of
edges between marked points or see a repeat and find a cyclic loop of edges.

Consider the marked curve $(C_{1},c_{1})$ that runs over the cycle or path.
For $\varepsilon>0$, let $w_{\varepsilon}(e)\coloneqq w(e)-\varepsilon
n_{c_{1}}(e)$. Then for $\varepsilon$ sufficiently small, $w_{\varepsilon}$
gives a weighted train-track structure on $T^{\prime\prime}$:

  * •

On an edge $e$, $w(e)>0$ by construction of $T^{\prime}$ so
$w_{\varepsilon}(e)\geq 0$; and

  * •

At a vertex $v$, the construction of $T^{\prime\prime}$ ensures that the
triangle inequalities at $v$ continue to hold in $w_{\varepsilon}$.

Let $\varepsilon_{1}$ be the maximum value of $\varepsilon$ so that
$(\Gamma,w_{\varepsilon_{1}},\tau)$ is a weighted train track. Let
$w_{1}=w_{\varepsilon_{1}}$ and $T_{1}=(\Gamma,w_{1},\tau)$. Consider the
derived train tracks $T_{1}^{\prime}$ (deleting edges of weight $0$) and
$T_{1}^{\prime\prime}$ (smoothing dominating vertices). By the choice of
$\varepsilon_{1}$, there is either

  * •

an edge $e$ of $T^{\prime\prime}$ with $w_{1}(e)=0$ but $w(e)\neq 0$, or

  * •

a vertex $v$ with a gate $g$ so that $w_{1}(g)$ dominates the other gates but
$w(g)$ does not.

In the first case,
$\lvert\operatorname{Edge}(T_{1}^{\prime\prime})\rvert<\lvert\operatorname{Edge}(T^{\prime\prime})\rvert$.
In the second case,
$\lvert\mathop{\mathrm{Yard}}(T_{1}^{\prime\prime})\rvert<\lvert\mathop{\mathrm{Yard}}(T^{\prime\prime})\rvert$.
In either case, by induction $T_{1}$ carries a marked weighted multi-curve
$(C_{2},c_{2})$ that saturates $T_{1}$. Then $c_{2}\sqcup c_{1}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC_{2}\sqcup C_{1}\to T$ is the desired multi-curve from the statement,
where $C_{1}$ has weight $\varepsilon_{1}$.

If we make a cyclic loop as soon as we see a repeated oriented edge, the
components of $C$ run over each (unoriented) edge at most twice. ∎

######  Lemma 3.17.

If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ is a map from a marked weighted graph to a marked graph and
$(C,c)$ is a marked weighted multi-curve carried by $W$ so that $f\circ c$ is
taut and $n_{f\circ c}=n_{f}$, then $f$ is taut.

###### Proof.

If $g\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ is any other map in $[f]$, then

$n_{g}\geq n_{g\circ c}\geq n_{[f\circ c]}=n_{f\circ c}=n_{f},$

using the fact that $W$ carries $c$ (and Lemma 2.13), the definition of
$n_{[f\circ c]}$ as an infimum over the homotopy class, and the hypotheses. ∎

######  Lemma 3.18.

A train-track map from a marked weighted train track is taut.

###### Proof.

Immediate from Proposition 3.16 and Lemma 3.17. ∎

###  3.3. Local models

To prove Theorem 3, we first analyze the situation locally in a regular
neighborhood of a singular value. This reduces to studying maps from a graph
with $k$ marked points to a $k$-leg star graph.

Let $\operatorname{Star}_{k}$ be the star graph with $k$ legs, with a central
vertex $s_{*}$, marked endpoints $s_{1},\dots,s_{k}$, and edges
$[s_{i},s_{*}]$. A _$k$ -marked_ graph is a graph with $k$ marked vertices
$\\{v_{i}\\}_{i=1}^{k}$ (in order). There is a canonical homotopy class of
marked maps from a $k$-marked graph to $\operatorname{Star}_{k}$, taking
$v_{i}$ to $s_{i}$. There is an analogue of Theorem 3 in this context.

######  Proposition 3.19.

Let $W$ be a $k$-marked weighted graph. Then there is a taut map in the
canonical homotopy class of maps to $\operatorname{Star}_{k}$. Furthermore,
the following conditions are equivalent.

  1. (1)

The map $f$ is taut.

  2. (2)

The graph $W$ carries a marked weighted train track $(T,t)$ so that $f\circ t$
is a train-track map and $n_{f\circ t}=n_{f}$.

  3. (3)

The graph $W$ carries a marked weighted curve $(C,c)$ so that $f\circ c$ is
taut and $n_{f\circ c}=n_{f}$.

######  Definition 3.20.

A _cut_ $S$ of a graph $\Gamma$ is a partition of the vertices of the graph
into two disjoint subsets: $\operatorname{Vert}(\Gamma)=S\sqcup\overline{S}$.
The corresponding _cut-set_ $c(S)=c(\overline{S})$ is the set of edges that
connect $S$ to $\overline{S}$. If $\Gamma$ has weights $w$, the _weight_ of
the cut is $w(S)\coloneqq\sum_{e\in c(S)}w(e)$.

Two cuts $S_{1}$ and $S_{2}$ are _nested_ if they are disjoint or one is
contained in the other : $S_{1}\cap S_{2}=\emptyset$, $S_{1}\subset S_{2}$, or
$S_{2}\subset S_{1}$. (It doesn’t matter if we replace $S_{1}$ with
$\overline{S_{1}}$ and/or replace $S_{2}$ with $\overline{S_{2}}$.)

Let $W$ be a $k$-marked weighted graph. A _$v_{i}$ -cut_ is a subset
$S_{i}\subset\operatorname{Vert}(G)$ so that
$S_{i}\cap\\{v_{1},\dots,v_{k}\\}=\\{v_{i}\\}$. A _vertex cut_ is a
$v_{i}$-cut for some $i$. A _minimal_ $v_{i}$-cut is one with minimal weight.
Let $\operatorname{mincut}_{i}(w)$ be the weight of a minimal $v_{i}$-cut.

######  Lemma 3.21.

If $S_{1}$ and $S_{2}$ are two cuts on the same weighted graph, then
$w(S_{1})+w(S_{2})\geq w(S_{1}\cap S_{2})+w(S_{1}\cup S_{2})$.

###### Proof.

This is the standard sub-modular property of cuts, and is easy to prove. ∎

######  Lemma 3.22.

If $W$ is a $k$-marked weighted graph and $S_{i}$ and $S_{i}^{\prime}$ are two
minimal $v_{i}$-cuts, then $S_{i}\cap S_{i}^{\prime}$ and $S_{i}\cup
S_{i}^{\prime}$ are also minimal $v_{i}$-cuts.

###### Proof.

The sets $S_{i}\cap S_{i}^{\prime}$ and $S_{i}\cup S_{i}^{\prime}$ are
$v_{i}$-cuts, so by minimality they all have weight at least as large as
$\operatorname{mincut}_{i}(w)=w(S_{i})=w(S_{i}^{\prime})$. Lemma 3.21 gives
the other inequality. ∎

######  Lemma 3.23.

If $W$ is a $k$-marked weighted graph, $S_{i}$ is a minimal $v_{i}$-cut, and
$S_{j}$ is a minimal $v_{j}$ cut for $j\neq i$, then $S_{i}\setminus S_{j}$ is
also a minimal $v_{i}$-cut and $S_{j}\setminus S_{i}$ is also a minimal
$v_{j}$-cut.

###### Proof.

$S_{i}\setminus S_{j}$ is a $v_{i}$-cut and $S_{j}\setminus S_{i}$ is a
$v_{j}$-cut. By minimality, their weights are at least as large as
$\operatorname{mincut}_{i}(w)$ and $\operatorname{mincut}_{j}(w)$,
respectively. Applying Lemma 3.21 to $S_{i}$ and $\overline{S_{j}}$ gives the
other inequalities. ∎

######  Definition 3.24.

If $W$ is a $k$-marked weighted graph, we say that an edge of $W$ is _slack_
if it has non-zero weight and is not contained in any minimal vertex cut. $W$
is _minimal_ if it has no slack edges.

See Figure 2 for the next two lemmas.

######  Lemma 3.25.

If $W=(\Gamma,w)$ is a weighted graph with $k$ marked vertices, then there is
a set of weights $w_{0}\leq w$ on $\Gamma$ so that $W_{0}=(\Gamma,w_{0})$ is
minimal and so that for all $i$,
$\operatorname{mincut}_{i}(w)=\operatorname{mincut}_{i}(w_{0})$.

###### Proof.

We proceed by induction on the number of slack edges. If $W$ is not minimal,
pick any slack edge $e_{0}$ of $W$. For $0\leq k\leq w(e_{0})$, define a
modified set of weights by

$w\\{e_{0}\mapsto k\\}(e)\coloneqq\begin{cases}k&e=e_{0}\\\
w(e)&\text{otherwise}.\end{cases}$

Let $k_{0}$ be minimal value so that, for all $i$,
$\operatorname{mincut}_{i}(w\\{\hbox{$e_{0}\mapsto
k_{0}$}\\})=\operatorname{mincut}_{i}(w)$. Then $k<w(e_{0})$ and $e$ is not
slack with respect to $w\\{e_{0}\mapsto k_{0}\\}$. By induction we can find
weights $w_{0}\leq w\\{e_{0}\mapsto k_{0}\\}\leq w$ on $\Gamma$ so that
$(\Gamma,w_{0})$ is minimal. ∎

######  Lemma 3.26.

Let $W=(\Gamma,w)$ be a $k$-marked weighted graph that is minimal and let
$\mathcal{S}\subset\mathcal{P}(\mathcal{P}(\operatorname{Vert}(W)))$ be a
nested set of minimal vertex cuts. Then there is a nested set of minimal
vertex cuts $\mathcal{T}\supset\mathcal{S}$ so that every edge of $W$ with
non-zero weight is contained in $c(S)$ for some $S\in\mathcal{T}$.

(Here $\mathcal{P}(X)$ is the power set of $X$.)

Figure 2. Finding minimum cuts and maximum flows near a vertex. Left: a
weighted graph $W$ with three marked vertices, with the weights indicated.
Minimal cuts that separate the vertices are marked; these are used to
construct a taut map from $W$ to $\operatorname{Star}_{3}$. Right: a weighted
graph $W_{0}$ carried by $W$, with minimal weights that have the same
$\operatorname{mincut}_{i}$ for each $i$. The minimal cuts on $W$ have been
extended to a complete nested family of minimal cuts. These are used to
construct a train track carried by $W$.

###### Proof.

We proceed by induction on the size of
$\operatorname{Edge}(W)\setminus\bigcup_{S\in\mathcal{S}}c(S)$. If there is at
least one edge $e_{1}$ in this set with non-zero weight, it is contained in
some minimal vertex cut-set $c(S_{1})$ by minimality of $W$. Then, by
repeatedly applying Lemmas 3.22 and 3.23, we can find another minimal vertex
cut $S_{1}^{\prime}$ so that $e\in c(S_{1}^{\prime})$ and $S_{1}^{\prime}$ is
nested with respect to all $S\in\mathcal{S}$. By induction,
$\mathcal{S}\cup\\{S_{1}^{\prime}\\}$ can be completed to the desired set
$\mathcal{T}$. ∎

###### Proof of Proposition 3.19.

We first prove the existence of a taut map. For each $i$, pick a minimal
$v_{i}$-cut $S_{i}$, and let $S_{i}^{\prime}=S_{i}\setminus\bigcup_{j\neq
i}S_{j}$. By Lemma 3.23, $\\{S_{i}^{\prime}\\}$ is a nested collection of
minimal $v_{i}$-cuts. Define $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\operatorname{Star}_{k}$ by mapping all vertices in $S_{i}^{\prime}$
to $s_{i}$, all vertices in
$\operatorname{Vert}(G)\setminus\bigcup_{i}S_{i}^{\prime}$ to $s_{*}$, and all
edges to reduced paths connecting their endpoints. (Thus $f$ is constant on
any edge not in any $c(S_{i}^{\prime})$.) Then $f$ is taut since the
$S_{i}^{\prime}$ are minimal.

Proposition 3.16 and Lemma 3.10 tell us that (2) implies (3), and Lemma 3.17
tells us that (3) implies (1), so it remains to prove that (1) implies (2).

Now suppose that $f$ is taut. For each regular value
$y\in[s_{*},s_{i}]\subset\operatorname{Star}_{k}$, consider the $v_{i}$-cut
$S_{y}=\\{v\in\operatorname{Vert}(\Gamma)\mid f(v)\in[s_{i},y]\\}$. Then
$S_{y}$ is a minimal vertex cut, since $f$ is taut. Furthermore, if $z$ is
another regular value of $f$ on any edge of $\operatorname{Star}_{k}$, then
$S_{y}$ and $S_{z}$ are nested. Let $\mathcal{S}=\\{\,S_{y}\mid
y\in\operatorname{Star}_{k},y\text{ regular}\,\\}$, considered as a nested
system of minimal cuts on $W$.

Use Lemma 3.25 to find weights $w_{0}\leq w$ so that $(\Gamma,w_{0})$ is
minimal. Let $\Gamma_{0}\subset\Gamma$ consist of the edges $e$ with
$w_{0}(e)\neq 0$, let $W_{0}=(\Gamma_{0},w_{0})$, and let $t\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW_{0}\hookrightarrow W$ be the inclusion. By Lemma 3.26, $\mathcal{S}$
can be completed to a nested system of cuts $\mathcal{T}$ on $W_{0}$ so that
every edge is in at least one cut-set.

For each $i$, let the distinct $v_{i}$-cuts in $\mathcal{T}$ be

$\\{v_{i}\\}=S_{i,0}\subsetneq S_{i,1}\subsetneq\dots\subsetneq S_{i,n_{i}}.$

For each $i$ and for $0\leq j\leq n_{i}$, pick distinct points
$x_{i,j}\in[s_{i},s_{*})\subset\operatorname{Star}_{k}$ with $x_{i,0}=s_{i}$
and with the $x_{i,j}$ in order. Then define a map $g\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW_{0}\to\operatorname{Star}_{k}$ on vertices by

$g(v)=\begin{cases}s_{i}&v=v_{i}\\\ x_{i,j}&v\in S_{i,j}\setminus S_{i,j-1}\\\
s_{*}&v\in\operatorname{Vert}(W_{0})\setminus\bigcup_{S\in\mathcal{T}}S.\end{cases}$

(These cases are exclusive since $\mathcal{T}$ is nested.) On an edge $e$ of
$W_{0}$, define $g(e)$ to be a reduced path connecting its endpoints. Since
$\mathcal{T}$ is a complete set of cuts, no edge maps to a single point. Let
$\tau_{0}=\tau(g)$. Then $(W_{0},\tau_{0})$ is a weighted train track: the
relevant triangle (in)equalities are implied by the fact that the $S_{i,j}$
are all minimal cuts.

By an appropriate choice of the $x_{i,j}$, the train-track map $g$ can be made
to be an arbitrarily small perturbation of $f\circ t$, so $f\circ t$ is also a
train-track map. If $e$ is an edge on which the original map $f$ is not
constant, then $e$ is not slack and $w(e)=w_{0}(e)$, so $n_{f\circ t}=n_{f}$
as desired. ∎

###  3.4. General flows

We now use these local models to prove Theorem 3.

######  Definition 3.27.

Let $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ be a PL map from a marked weighted graph $W$ to a marked
graph $\Gamma$. Pick $y\in\Gamma$ and let $N\subset\Gamma$ be a closed regular
neighborhood of $y$. Then the _local model for $f$ at $y$_ is the map

$f^{-1}(N)/\mathord{\sim}\longrightarrow N,$

where

  * •

$N$ is considered as a marked graph (equivalent to $\operatorname{Star}_{k}$)
with marked points at $\partial N$;

  * •

$\sim$ is the equivalence relation that identifies two points in
$f^{-1}(\partial N)$ if they map to the same point in $\partial N$; and

  * •

$f^{-1}(N)/\mathord{\sim}$ is considered as a $k$-marked weighted graph, with
weights inherited from $W$.

######  Lemma 3.28.

Let $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ be a homotopy class of maps from a marked weighted graph $W$
to a marked graph $\Gamma$. Then there is a locally taut map in $[f]$.

###### Proof.

Suppose $f$ is any PL representative for its homotopy class. We can modify $f$
to send vertices to vertices without increasing $n_{f}$, as follows. For each
edge $e$ of $\Gamma$, look at the division of $e$ into intervals according to
the value of $n_{f}$. Pick one of these intervals on which $n_{f}$ is minimal
(among the values of $n_{f}$ that appear), and spread out this interval by a
homotopy until it covers $e$. This gives us an initial map $f_{0}$.

If $f_{0}$ is not locally taut, then there is some vertex $v$ of $\Gamma$ so
that the local model of $f_{0}$ at $v$ is not taut. By Proposition 3.19, there
is a taut map in the homotopy class of the local model. Let $f_{0}^{\prime}$
be $f_{0}$ with the map replaced by its taut model near $v$. There is at least
one edge $e_{0}$ of $\Gamma$ with a segment near $v$ on which
$n_{f_{0}^{\prime}}<n_{f_{0}}$. Homotop $f_{0}^{\prime}$ as above, spreading
out segments of minimal multiplicity, to construct a map $f_{1}$ that sends
vertices to vertices with $n_{f_{1}}\leq n_{f_{0}}$ everywhere and
$n_{f_{1}}(e_{0})<n_{f_{0}}(e_{0})$.

If $f_{1}$ is not locally taut, repeat the process, with $f_{1}$ in place of
$f_{0}$. Our initial representative $f_{0}$ gives an upper bound on
$n_{f_{i}}(e)$ for all $e$. There are only finitely many linear combinations
of the non-zero weights of edges of $W$ to get a value less than this bound.
At each step $n_{f}$ strictly decreases on at least one edge, so the process
terminates in finite time. ∎

###### Proof of Theorem 3.

We first prove the equivalence of the four conditions on taut maps. (1)
implies (2) is obvious.

To see that (2) implies (3), suppose $f$ is locally taut. Then for each
singular value $y\in\Gamma$, the local model for $f$ at $y$ carries a weighted
train track compatible with $f$ by Proposition 3.19. Define a weighted train
track $T$ and map $t\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muT\to W$ by assembling these local models following the pattern of $W$,
leaving $W$ unchanged outside of the local models. Then $(T,t)$ is the desired
train track carried by $W$, with $T$ a subgraph of $W$.

Proposition 3.16 shows that (3) implies (4).

Lemma 3.17 shows that (4) implies (1).

Now if $[f]$ is any homotopy class, by Lemma 3.28 there is a locally taut
element of $[f]$, which by the above equivalences is also globally taut.

The statements about saturation follow immediately. ∎

###  3.5. Connection to max-flow/min-cut

We can connect Theorem 3 and Proposition 3.19 to a statement that looks more
like the classical max-flow/min-cut problem (Example 3.9). For simplicity, we
restrict to the local setting of Proposition 3.19. Given a graph $\Gamma$ with
$k$ marked points $\\{v_{i}\\}_{i=1}^{k}$, define a _flow_ from $v_{i}$ to
$v_{j}$ to be a marked weighted multi-curve $(C,c)$ on $\Gamma$, with each
component a marked interval with one endpoint mapping to $v_{i}$ and the other
mapping to $v_{j}$. Such a flow has multiplicities $n_{c}$ on each edge as
usual, as well as a total weight $w(c)$, the sum of the weights of all
components of $C$.

######  Corollary 3.29.

Let $W$ be a weighted graph with $k$ marked points $\\{v_{i}\\}_{i=1}^{k}$.
Then we can find

  * •

for $1\leq i\leq k$, a $v_{i}$-cut $S_{i}$, and

  * •

for $1\leq i<j\leq k$, a flow $c_{ij}=c_{ji}$ from $v_{i}$ to $v_{j}$

so that

  * •

the collection of all flows $c_{ij}$ is carried by $W$: for each edge $e$ of
$\Gamma$,

(3.30) $\sum_{i<j}n_{c_{ij}}(e)\leq w(e),$

  * •

the total flow into a vertex equals the weight of the cut: for each $i$,

(3.31) $\sum_{j\neq i}w(c_{ij})=w(S_{i}).$

In this situation, for each $i$, $w(S_{i})$ is minimal and $\sum_{j\neq
i}w(c_{ij})$ is maximal.

###### Proof.

Let $f$ be a taut map in the canonical homotopy class of maps from $W$ to
$\operatorname{Star}_{k}$, as given by Proposition 3.19. By that proposition,
$W$ carries a marked weighted multi-curve $(C,c)$ so that $f\circ c$ is taut
and $n_{f\circ c}=n_{f}$. The only non-trivial homotopy classes of marked
multi-curves on $\operatorname{Star}_{k}$ are given by paths connecting
$s_{i}$ to $s_{j}$ for some $i\neq j$. Let the flow $c_{ij}$ be the flow given
by those components of $(C,c)$ that connect $v_{i}$ to $v_{j}$. Then Equation
(3.30) says that $W$ carries $(C,c)$.

On the other hand, for each $i$, let $y_{i}$ be a regular value on
$[s_{*},s_{i}]$, and let $S_{i}$ be $S_{y_{i}}$ as defined in the proof of
Proposition 3.19. Then the equality $n_{f\circ c}(y)=n_{f}(y)$ is equivalent
to Equation (3.31). Minimality of $w(S_{i})$ and maximality of $\sum_{j\neq
i}w(c_{ij})$ both follow from tautness, and indeed are easy to deduce from
Equation (3.31). ∎

###  3.6. Strongly reduced maps

We introduce a stronger notion of “reduced” for maps between general marked
graphs without a weight structure.

######  Definition 3.32.

A map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ between marked graphs is _strongly reduced_ if
it is taut for some choice of positive weights on $\Gamma_{1}$. See Figure 3
for a non-example.

Figure 3. A map from an eyeglass graph to a theta graph that is reduced but
not strongly reduced.

######  Lemma 3.33.

Let $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ be an edge-reduced map. Then $f$ is strongly
reduced iff for each edge $e$ of $\Gamma_{1}$, either $f$ is constant on $e$
or there is a reduced curve $(C,c)$ on $\Gamma_{1}$ that runs over $e$ and so
that $f\circ c$ is also reduced. Furthermore, the curves can be chosen to run
over each edge of $\Gamma_{1}$ at most twice.

###### Proof.

The first part is a consequence of the equivalence of conditions (1) and (4)
in Theorem 3.

For the second part, use Proposition 3.16. ∎

######  Definition 3.34.

Given an edge-reduced PL map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ between marked graphs, the _combinatorial type_
of $f$ consists of the following discrete data.

  1. (1)

For each vertex $v$ of $\Gamma_{1}$, record whether $f(v)$ is on an vertex or
in the interior of an edge of $\Gamma_{2}$, and which vertex or edge it lies
on.

  2. (2)

For each oriented edge $\vec{e}$ of $\Gamma_{1}$, record the _edge-path_ of
$f(\vec{e})$, the reduced sequence of oriented edges of $\Gamma_{2}$ that
$f(\vec{e})$ travels over. This edge-path may start and/or end with a partial
edge, depending on whether the endpoints of $\vec{e}$ map to vertices or
edges. There are degenerate cases when $\vec{e}$ maps to a single vertex or
stays within the interior of a single edge.

The combinatorial type of $f$ determines the homotopy class of $[f]$.

######  Proposition 3.35.

Let $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ be a homotopy class of maps between marked
graphs. Then there are only finitely many combinatorial types of strongly
reduced maps in $[f]$.

###### Proof.

Let $g\in[f]$ be strongly reduced, and let $\vec{e}$ be an oriented edge of
$\Gamma_{1}$. We must show that there is a finite set of possible edge-paths
for $f(\vec{e})$. For this, we apply Lemma 3.33. Either $f$ is constant on $e$
(with only finitely many combinatorial possibilities), or else there is a
multi-curve $(C,c)$ running over $e$ as in the statement. Since $(C,c)$ runs
over each edge of $\Gamma_{1}$ at most twice, there are only finitely many
possibilities for it. Furthermore, $[f\circ c]$ is determined by $[f]$ and
$[c]$, so there are only finitely many edge-paths in $\Gamma_{2}$ arising from
$[f\circ c]$. The edge-path of $f(\vec{e})$ must be a sub-path of the edge-
path of $f\circ c$, and again there are only finitely many possibilities. ∎

######  Remark 3.36.

Proposition 3.35 is false if we look at reduced maps rather than strongly
reduced maps. (The map $f$ can be “spun” around a taut cycle of $\Gamma_{1}$.)

###  3.7. Restricting the domain and range

######  Lemma 3.37.

Let $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ be a map from a marked weighted graph to a marked graph. Let
$W_{0}\subset W$ be the closure of the subset where $w(x)\neq 0$. Then $f$ is
taut iff the restriction $f|_{W_{0}}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW_{0}\to\Gamma$ is taut.

###### Proof.

Segments of weight $0$ do not effect $n_{f}$. ∎

######  Definition 3.38.

A homotopy class $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ of marked maps is _essentially surjective_ if
every element of $[f]$ is surjective.

######  Remark 3.39.

If $\Gamma_{1}$ and $\Gamma_{2}$ are connected with no marked points and no
unmarked 1-valent vertices, then if $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ is $\pi_{1}$-surjective it is essentially
surjective.

If $f$ is not (essentially) surjective, then tautness of $f$ is equivalent to
tautness of the map with restricted range.

######  Lemma 3.40.

Let $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma$ be a map from a marked weighted graph to a marked graph.
Suppose the image of $f$ is contained in a subgraph $\Gamma_{0}\subset\Gamma$.
Let $\Gamma^{*}$ be $\Gamma$ with all edges not in $\Gamma_{0}$ collapsed,
with $\kappa\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma\to\Gamma^{*}$ the collapsing map. Then the following are
equivalent:

  1. (1)

$f$ is taut,

  2. (2)

the map with restricted range $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma_{0}$ is taut, and

  3. (3)

the map $\kappa\circ f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW\to\Gamma^{*}$ is taut.

###### Proof.

Recall from Theorem 3 that being taut is equivalent to being locally taut. If
you replace “taut” with “locally taut” in conditions (1)– (3) above, they are
easily seen to be equivalent. ∎

###  3.8. Continuity

Let $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu(\Gamma_{1},w)\to\Gamma_{2}$ be a homotopy class of maps between marked
graphs. We are interested in how $n^{w}_{[f]}$ varies as $w$ varies. Define
$N_{[f]}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\mathcal{W}(\Gamma_{1})\to\mathcal{W}(\Gamma_{2})$ by
$N_{[f]}(w)\coloneqq n_{[f]}^{w}$. (There is usually no single $g\in[f]$ that
is taut for all $w$.)

######  Proposition 3.41.

Let $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ be a homotopy class of maps between marked
graphs. Then $N_{[f]}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\mathcal{W}(\Gamma_{1})\to\mathcal{W}(\Gamma_{2})$ is continuous.

###### Proof.

Pick $w_{0}\in\mathcal{W}(\Gamma_{1})$ and
$e_{0}\in\operatorname{Edge}(\Gamma_{2})$, and let $K=n_{[f]}^{w_{0}}(e_{0})$.
Suppose that $w\in\mathcal{W}(\Gamma_{1})$ is some set of weights with $\lvert
w(e)-w_{0}(e)\rvert<\varepsilon$ for all $e$. To show continuity of $N_{[f]}$
near $w_{0}$, we will give upper and lower bounds on $n^{w}_{[f]}(e_{0})$ in
terms of $K$ and $\varepsilon$.

To get an upper bound, let $f_{0}\in[f]$ be a taut map from
$(\Gamma_{1},w_{0})$ to $\Gamma_{2}$. Pick a regular value $y\in e_{0}$ of
$f_{0}$, and let $k=\lvert f_{0}^{-1}(y)\rvert$. Then since $f_{0}\in[f]$,

$n_{[f]}^{w}(e_{0})\leq n_{f_{0}}^{w}(y)\leq
n_{f_{0}}^{w_{0}}(y)+k\varepsilon=K+k\varepsilon,$

as desired.

To get a lower bound, let $E_{1}=\\{\,e\in\operatorname{Edge}(\Gamma_{1})\mid
w_{0}(e)\neq 0\,\\}$ and $\nu=\min_{e\in E_{1}}w_{0}(e)$. Make sure
$\varepsilon<\nu$, and let $M=K/(\nu-\varepsilon)$. Let $g\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu(\Gamma_{1},w)\to\Gamma_{2}$ be a taut map in $[f]$. Now
$n_{g}^{w}(e_{0})$ can be written as an integer linear combination of weights
of edges:

$n_{g}^{w}(e_{0})=\sum_{e\in\operatorname{Edge}(\Gamma_{1})}a_{e}w(e).$

If $n_{g}^{w}(e_{0})\geq K$, we are done. Otherwise, we must have $\sum_{e\in
E_{1}}a_{e}\leq M$, and so

$\displaystyle n_{g}^{w}(e_{0})$ $\displaystyle\geq\sum_{e\in E_{1}}a_{e}w(e)$
$\displaystyle\geq-M\varepsilon+\sum_{e\in\operatorname{Edge}(\Gamma_{1})}a_{e}w_{0}(e)$
$\displaystyle\geq-M\varepsilon+K.$

The last inequality uses $n_{g}^{w_{0}}(e_{0})\geq K$, which follows from the
definition of $K$. ∎

######  Proposition 3.42.

Let $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ be a homotopy class of maps between marked
graphs. Then $N_{[f]}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\mathcal{W}(\Gamma_{1})\to\mathcal{W}(\Gamma_{2})$ is piecewise-linear.

###### Proof.

By Proposition 3.41, we may restrict attention to positive weights
$w\in\mathcal{W}^{+}(\Gamma_{1})$. Then $n^{w}_{[f]}(e)$ can be computed by
taking a taut representative $g\in[f]$ and finding $g^{-1}(x)$ for $x$ a
generic point on $e$ close to one of the endpoints. The combinatorial type of
$g$ determines $g^{-1}(x)$, and Proposition 3.35 there are only finitely many
possibilities for $g^{-1}(x)$. For each possibility, $n_{g}(e)$ is an integer
linear combination of weights on $\Gamma_{1}$. By definition $n^{w}_{[f]}(e)$
is the minimum these possibilities, so $N_{[f]}$ is a minimum of a finite set
of linear functions. ∎

##  4\. Weak graphs and Lipschitz energy

We now turn to minimizing the Lipschitz stretch factor of maps between graphs.

######  Theorem 4 (White).

Let $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ be a homotopy class of maps between marked length graphs.
Then there is a representative $\psi\in[\phi]$ and a marked curve
$c\nobreak\mskip 2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip
6.0mu plus 1.0muC\to K_{1}$ so that the sequence

$C\overset{c}{\longrightarrow}K_{1}\overset{\psi}{\longrightarrow}K_{2}$

is tight. In particular,

$\operatorname{Lip}[\phi]=\operatorname{Lip}(\psi)=\frac{\ell[\psi\circ
c]}{\ell[c]}=\sup_{c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to K_{1}}\frac{\ell[\psi\circ c]}{\ell[c]},$

where the supremum runs over all non-trivial curves. We get the same quantity
if we take the supremum over multi-curves or over curves that cross each edge
of $K_{1}$ at most twice.

A version of Theorem 4 appears in papers by Bestvina [Bes11, Proposition 2.1]
and Francaviglia-Martino [FM11, Proposition 3.11], and is attributed to Tad
White (unpublished). Both papers work in the context of outer space and so
assume that $\phi$ is a homotopy equivalence, although that assumption is
never used in the proof. The extension to marked graphs is also immediate.

We need an extension of Theorem 4: we will need to understand the behavior of
energies on the boundary of $\mathcal{L}^{+}(\Gamma)$. This leads us to _weak
graphs_ , in which edges may have length $0$. The definition of maps between
weak graphs requires a little care, since we remember homotopy information
that may not be present at the level of the collapsed graph.

######  Definition 4.1.

A _weak graph_ is a graph $\Gamma$ in which certain edges are designated as
_null edges_ ; the union of the null edges forms the _null graph_. The
_collapsed graph_ $\Gamma^{*}$ of $\Gamma$ is the graph obtained by
identifying each null edge to a single point. There is a natural _collapsing
map_ $\kappa\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma\to\Gamma^{*}$. Observe that $\kappa$ is a homotopy equivalence iff
the null graph is a forest.

If $(\Gamma,\ell)$ is a weak length graph, we consider $\Gamma$ to be a weak
graph, where the null edges are the edges of length $0$. The lengths $\ell(e)$
determine a pseudo-metric on $\Gamma$ and a metric on $\Gamma^{*}$.

If $\Gamma_{1}$ and $\Gamma_{2}$ are weak graphs, a PL _weak map_ from
$\Gamma_{1}$ to $\Gamma_{2}$ is a pair $(\widetilde{f},f)$ of a PL map
$f\nobreak\mskip 2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip
6.0mu plus 1.0mu\Gamma_{1}^{*}\to\Gamma_{2}^{*}$ between the collapsed graphs,
together with a map $\widetilde{f}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ that is a local homotopy lift of $f$, in the
following sense. Pick disjoint regular neighborhoods $N_{v}^{*}$ of each
vertex $v$ of $\Gamma_{2}^{*}$. Let
$N_{2}^{*}=\bigcup_{v}N_{v}^{*}\subset\Gamma_{2}^{*}$,
$N_{1}^{*}=f^{-1}(N_{2}^{*})$, $N_{2}=\kappa_{2}^{-1}(N_{2}^{*})$, and
$N_{1}=\kappa_{1}^{-1}(N_{1}^{*})$. Then we require that
$N_{1}=\widetilde{f}^{-1}(N_{2})$ and that the diagram

(4.2)
$\Gamma_{1}$$\Gamma_{2}$$\Gamma_{1}^{*}$$\Gamma_{2}^{*}$$\scriptstyle{\widetilde{f}}$$\scriptstyle{f}$$\scriptstyle{\kappa_{1}}$$\scriptstyle{\kappa_{2}}$

commutes up to a homotopy that is the identity on $\Gamma_{1}\setminus N_{1}$.

$\Gamma_{1}$$\Gamma_{2}$$\Gamma_{2}^{*}$$\scriptstyle{\widetilde{f}}$$\scriptstyle{f}$$\scriptstyle{\kappa}$
Figure 4. A weak map where an exact lift is impossible. On the right is a weak
graph $\Gamma_{2}$, with the red loop declared to be a null edge, and the
collapsed graph $\Gamma_{2}^{*}$. The map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}^{*}$ maps the edge of $\Gamma_{1}$ forward and
backward over the edge of $\Gamma_{2}^{*}$, so that the inverse image of the
vertex $v$ is a single point. The local lift $\widetilde{f}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ maps the edge of $\Gamma_{1}$ around the null
loop.

We do not require that $\widetilde{f}$ is an exact lift of $f$, as those do
not always exist; see Figure 4.

When we speak about an _energy_ of a weak map $(\widetilde{f},f)$ (with some
additional structure on the graphs, as appropriate), we mean the energy of the
map $f$ between collapsed graphs, using the same analytic expression as for
maps between ordinary graphs. This applies to all of the energies we have
introduced so far, including the Dirichlet, Lipschitz, and embedding energies.
On the other hand, by the _homotopy class_ of the weak map we mean the
homotopy class $[\widetilde{f}]$ of the map between the uncollapsed graphs. If
the null graphs have non-trivial $\pi_{1}$, then $[f]$ will have less
information than $[\widetilde{f}]$.

Two weak maps $(\widetilde{f},f)$ and $(\widetilde{g},g)$ are equal if $f=g$
and $\widetilde{f}$ and $\widetilde{g}$ are locally homotopic.

We next generalize the notions of reduced maps.

######  Definition 4.3.

Let $(\widetilde{f},f)\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu(\Gamma_{1},\Gamma_{1}^{*})\to(\Gamma_{2},\Gamma_{2}^{*})$ be a weak
marked map. Suppose we have point $y\in\Gamma_{2}^{*}$, a regular neighborhood
$N_{y}^{*}$ of $y$, and a component $Z$ of
$\kappa_{1}^{-1}(f^{-1}(N_{y}^{*}))$ that is not an entire component of
$\Gamma_{1}$. Then we say that $Z$ is a _dead end_ of $f$ if $\widetilde{f}$
can be changed by a local homotopy so that $\widetilde{f}(Z)$ does not
intersect $\kappa_{2}^{-1}(y)$. Concretely, we have the following, where
$N_{y}=\kappa_{2}^{-1}(N_{y}^{*})$.

  1. (1)

If $Z$ contains a marked point, then $Z$ is not a dead end.

  2. (2)

If there are two points $x_{1},x_{2}\in\partial Z$ so that
$\widetilde{f}(x_{1})$ and $\widetilde{f}(x_{2})$ are distinct points of
$\partial N_{y}$, then $Z$ is not a dead end.

  3. (3)

If there are points $x_{1},x_{2}\in\partial Z$ (possibly identical) and a path
$\gamma$ in $Z$ between them so that
$\widetilde{f}(x_{1})=\widetilde{f}(x_{2})$ and $\widetilde{f}(\gamma)$ is
non-trivial in $\pi_{1}(N_{y},\widetilde{f}(x_{1}))$, then $Z$ is not a dead
end.

  4. (4)

Otherwise, $Z$ is a dead end.

If $(\widetilde{f},f)$ has no dead ends, we say that it is _reduced_. As with
non-weak maps, we can _reduce_ dead ends: if $Z$ is a dead end mapping to
$y\in\Gamma_{2}^{*}$, modify $f$ so that $f(\kappa_{2}(Z))$ misses $y$ and
continue to pull until you reach another singular value of $f$.

######  Proposition 4.4.

Every weak map is homotopic to a reduced map. Reduction does not increase
$E^{p}_{q}$ for any $p\leq q$.

###### Proof.

As in Proposition 3.4, repeatedly reduce dead ends. As in Proposition 3.5,
energies are clearly not increased. ∎

######  Theorem 4′.

Let $[\phi]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ be a homotopy class of maps between weak marked length
graphs, so that $K_{1}$ has at least one non-null edge and so that no null
cycle in $K_{1}$ maps to a non-null cycle in $K_{2}$. Then there is a weak map
$\psi\in[\phi]$ and a marked curve $c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to K_{1}$ with $\ell[c]>0$ so that the sequence

$C\overset{c}{\longrightarrow}K_{1}\overset{\psi}{\longrightarrow}K_{2}$

is tight. In particular,

$\operatorname{Lip}[\phi]=\operatorname{Lip}(\psi)=\frac{\ell[\psi\circ
c]}{\ell[c]}=\sup_{\begin{subarray}{c}c\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muC\to K_{1}\\\ \ell[c]>0\end{subarray}}\frac{\ell[\psi\circ c]}{\ell[c]},$

where the supremum runs over all curves $c$ of positive length in $K_{1}$. We
get the same quantity if we take the supremum over multi-curves or over curves
that cross each edge of $K_{1}$ at most twice.

To prove Theorem 4′, we use a finite-dimensional approximation to the space of
all maps from $K_{1}$ to $K_{2}$. We first treat the case of ordinary (non-
weak) maps.

######  Definition 4.5.

A PL map $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ between marked length graphs is _constant-derivative_ if
it is edge-reduced and $\lvert f^{\prime}\rvert$ is constant on each edge of
$K_{1}$. A constant-derivative map is determined by its combinatorial type
(Definition 3.34) plus a bounded amount of continuous data: for each vertex
$v$ of $K_{1}$ that maps to the interior of an edge $e$ of $K_{2}$, record
where $f(v)$ is along $e$. Thus we can assemble the constant-derivative maps
in $[f]$ into a locally-finite polyhedral complex $\operatorname{PL}^{*}[f]$
of dimension at most $\lvert\operatorname{Vert}(K_{1})\rvert$. For $D>0$ a
constant, let $\operatorname{PL}^{*}[f]_{\leq D}$ be the subspace of
$\operatorname{PL}^{*}[f]$ with Lipschitz constant $\leq D$.

######  Lemma 4.6.

For any homotopy class $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ of maps between marked length graphs and any $D>0$, the
space $\operatorname{PL}^{*}[f]_{\leq D}$ is a compact polyhedral complex.

###### Proof.

The bound on derivatives gives a bound on how many edges of $K_{2}$ the image
of an edge of $K_{1}$ can cross. Therefore only finitely many different cells
of $\operatorname{PL}^{*}[f]$ intersect $\operatorname{PL}^{*}[f]_{\leq D}$. ∎

We now turn to versions of Definitions 3.34 and 4.5 for weak maps.

######  Definition 4.7.

The _combinatorial type_ of an edge-reduced weak map
$(\widetilde{f},f)\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ consists of the following discrete data.

  * •

For each vertex $v$ of $\Gamma_{1}^{*}$, record whether $f(v)$ is on a vertex
or in the interior of an edge of $\Gamma_{2}^{*}$, and which vertex or edge it
lies on.

  * •

Record the homotopy class $[\widetilde{f}]$.

If we want to make this parallel to Definition 3.34, the homotopy class of
$\widetilde{f}$ is conveniently recorded by picking, for each vertex $v$ of
$\Gamma_{1}$, a lift of $f(\kappa_{1}(v))$ to a point
$\widetilde{f}(v)\in\Gamma_{2}$, and then recording, for each oriented edge
$\vec{e}$ of $\Gamma_{1}$, the reduced sequence of (partial) edges that
$\widetilde{f}(\vec{e})$ passes over. But this is not uniquely specified by
the homotopy class of $\widetilde{f}$: different choices of lifts of
$f(\kappa_{1}(v))$ will lead to different sequences of edges in
$\widetilde{f}(\vec{e})$. The combinatorial type of $(\widetilde{f},f)$ does
not depend on this auxiliary choice of lift.

######  Definition 4.8.

A weak PL map $(\widetilde{f},f)\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ between weak marked length graphs is _constant
derivative_ if it is edge-reduced and $\lvert f^{\prime}\rvert$ is constant on
each non-null edge of $K_{1}$. As before, we can assemble the constant-
derivative maps in $[f]$ into a polyhedral complex $\operatorname{PL}^{*}[f]$
of dimension at most $\lvert\operatorname{Vert}(K_{1}^{*})\rvert$, with one
cell per combinatorial type. If we give an upper bound on
$\operatorname{Lip}(f)$, we get a subcomplex $\operatorname{PL}^{*}[f]_{\leq
D}$.

######  Lemma 4.9.

For any homotopy class $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muK_{1}\to K_{2}$ of maps between weak marked length graphs and constant
$D>0$, the space $\operatorname{PL}^{*}[f]_{\leq D}$ is a compact polyhedral
complex.

###### Proof.

As in Lemma 4.6, for any non-null edge $e$, the bound on
$\operatorname{Lip}(f)$ gives a bound on how many edges of $K_{2}^{*}$ can be
crossed by $f(e)$. The rest of the data is the homotopy class, which is fixed
by definition (and also determines the homotopy class of the local lifts). ∎

###### Proof of Theorem 4′.

We follow the previous proofs [Bes11, FM11], adapted to the setting of weak
maps between marked graphs.

First, we may assume a weak map in $[\phi]$ of minimal Lipschitz energy is in
$\operatorname{PL}^{*}[\phi]$. The condition that no null cycle of $K_{1}$
maps to a non-null cycle of $K_{2}$ guarantees that there is some weak map
$(\widetilde{\psi}_{0},\psi_{0})\in\operatorname{PL}^{*}[\phi]$ of finite
Lipschitz energy. Then any optimizer $(\widetilde{\psi},\psi)$ must be in
$\operatorname{PL}^{*}[\phi]_{\leq\operatorname{Lip}(\psi_{0})}$. By Lemma 4.9
we are minimizing a continuous function over a compact set, so the minimum is
achieved. Let $(\widetilde{\psi},\psi)\in\operatorname{PL}^{*}[\phi]$ realize
$\operatorname{Lip}[\phi]$.

Next we prove the existence of a marked curve $c$ exhibiting the Lipschitz
stretch of $\psi$. For each non-null edge $e$ of $K_{1}$, say that it is

  * •

a _tension edge_ if $\lvert\psi^{\prime}(e)\rvert$ is the maximal value,
$\operatorname{Lip}(\psi)$, and

  * •

a _slack edge_ if $\lvert\psi^{\prime}(e)\rvert<\operatorname{Lip}(\psi)$.

Assume that the set of tension edges of $\psi$ is minimal among maps with
minimal $\operatorname{Lip}(\psi)$.

To find the desired curve, we will find a suitable sequence of oriented edges
$(\vec{e}_{i})_{i=1}^{N}$ of $K_{1}$ passing only over tension and null edges.

######  Lemma 4.10.

In the setting above, let $\vec{e}_{0}$ be an oriented tension edge of
$K_{1}$. Then we can find a reduced sequence of edges
$\vec{e}_{1},\dots,\vec{e}_{k}$ on $K_{1}$ so that either

  * •

the $\vec{e}_{i}$ for $i=1,\dots,k$ are null edges and $\vec{e}_{k}$ ends at a
marked point, or

  * •

the $\vec{e}_{i}$ for $i=1,\dots,k-1$ are null edges and $\vec{e}_{k}$ is a
tension edge.

In either case, $(\psi(\vec{e}_{0}),\dots,\psi(\vec{e}_{k}))$ is also reduced.

###### Proof.

Let $C_{1}$ be the connected component of the null graph of $K_{1}$ that
contains the end of $\vec{e}_{0}$ and let $\\{x\\}=\kappa_{1}(C_{1})$. Let
$y=\psi(x_{1})$ and $C_{2}$ be the relevant component of $\kappa_{2}^{-1}(y)$.
$C_{2}$ may be a point on an edge of $K_{2}$, a vertex of $K_{2}$, or a
connected null subgraph of $K_{2}$. We proceed by cases on $C_{1}$ and
$C_{2}$, parallel to the cases in Definition 4.3.

  1. (1)

If $C_{1}$ has a marked point $x$, connect the end of $\vec{e}_{0}$ to $x$
through null edges.

  2. (2)

If there is another tension edge $\vec{f}$ of $K_{1}$ incident to $C_{1}$ so
that $\vec{f}$ and the reverse of $\vec{e}_{0}$ map by $\psi\circ\kappa$ to
distinct directions in $K_{2}^{*}$, connect $\vec{e}_{0}$ to $\vec{f}$ by a
reduced path in $K_{1}$.

  3. (3)

If $\pi_{1}(C_{1})$ maps non-trivially to $\pi_{1}(C_{2})$, connect
$\vec{e}_{0}$ to its reverse by a reduced loop in $C_{1}$ that maps to a non-
trivial loop in $C_{2}$.

  4. (4)

If none of the above cases apply, we get a contradiction, as follows.
Partition the non-null edges incident to $C_{1}$ according to which direction
they map to from $y$. (Put each edge with $\lvert\psi^{\prime}\rvert=0$ into
its own part.) Since we are not in cases (1) or (3), we can displace $y\in
K_{2}^{*}$ in any direction, reducing $\lvert\psi^{\prime}\rvert$ on one group
of edges at the cost of increasing it on all other groups. Since we are not in
case (2), we can reduce $\lvert\psi^{\prime}(\vec{e}_{0})\rvert$ so $e_{0}$ is
no longer a tension edge without creating another tension edge, contradicting
the assumption that the set of tension edges of $\psi$ was minimal.

In any of cases (1)–(3), by construction the sequence of edges in $K_{1}$ is
reduced, and the path in $K_{2}$ falls into one of the cases of Definition 4.3
and so is reduced as a weak map.∎

To complete the proof of Theorem 4′, start with any tension edge $\vec{e}_{0}$
of $K_{1}$. (There is at least one since not all edges of $K_{1}$ are null.)
Use Lemma 4.10 to construct a non-backtracking chain of tension and null edges
forward and backward from $\vec{e}_{0}$. Either the chain ends in a marked
point both forward and backward, or there is a repeated oriented edge. In
either case we can extract a marked curve $c$ (either an interval or a cycle)
so that both $c$ and $\psi\circ c$ are (weakly) reduced. Thus
$\operatorname{Lip}(\psi)=\ell(\psi\circ c)/\ell(c)=\ell[\psi\circ
c]/\ell[c]$. If we make the null paths as efficient as possible and close off
to make a cycle the first time that an oriented edge is repeated in the chain,
then $c$ will cross each (unoriented) edge of $K_{1}$ at most twice. ∎

######  Remark 4.11.

The proof of Theorem 4′ is similar to the proof of Proposition 3.16. The
presence of null edges introduces extra complications in Theorem 4′.

##  5\. Harmonic maps

###  5.1. Definition and existence

In this section, we give a concrete description of harmonic maps and prove
their existence, making the intuitive description of harmonic maps from the
introduction more precise. See Section 1.1 for a summary of prior work.

######  Definition 5.1.

Let $G=(\Gamma,\alpha)$ be a marked elastic graph and let $K$ be a marked
length graph. Recall from Definition 4.5 that $\operatorname{PL}^{*}[f]$ is
the space of PL maps for which $\lvert f^{\prime}\rvert$ is constant on each
edge of $G$. To any constant-derivative map $f$, we can associate the
_tension-weighted graph_ $W_{f}=(\Gamma,\lvert f^{\prime}\rvert)$; that is,
the weight of an edge $e$ is $\lvert f^{\prime}(e)\rvert$. Then $f$ is
_harmonic_ if it is constant-derivative and the associated map
$f\nobreak\mskip 2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip
6.0mu plus 1.0muW_{f}\to K$ is taut.

In general, it is not immediately obvious when a map is taut. We can simplify
the condition in Definition 5.1 to give the triangle inequalities at vertices
from the introduction.

######  Proposition 5.2.

Let $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to K$ be a constant-derivative map from a marked elastic graph to a
marked length graph. Let $G_{0}\subset G$ be the subgraph of $G$ on which
$\lvert f^{\prime}\rvert\neq 0$, and let $f_{0}$ be the restriction of $f$ to
$G_{0}$. Then $f$ is harmonic iff $(W_{f_{0}},\tau(f_{0}))$ forms a marked
weighted train track according to Definition 3.14.

###### Proof.

By Lemma 3.37, $f$ is harmonic iff $f_{0}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW_{f_{0}}\to K$ is taut. If $f_{0}$ is taut, the train-track in condition
(3) of Theorem 3 must be $(W_{f_{0}},\tau(f_{0}))$. ∎

######  Theorem 5.

Let $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to K$ be a homotopy class of maps from a marked elastic graph to a
marked length graph. Then there is a harmonic map in $[f]$. Furthermore, the
following conditions are equivalent.

  1. (1)

The map $f$ is a global minimum for $\operatorname{Dir}$.

  2. (2)

The map $f$ is a local minimum for $\operatorname{Dir}$.

  3. (3)

The map $f$ is harmonic.

  4. (4)

The natural map $\iota\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muW_{f}\to G$ is part of a tight sequence

$W_{f}\overset{\iota}{\longrightarrow}G\overset{f}{\longrightarrow}K.$

  5. (5)

There is a weighted multi-curve $(C,c)$ on $G$ that forms a tight sequence

$C\overset{c}{\longrightarrow}G\overset{f}{\longrightarrow}K.$

###### Proof.

We start with the equivalences. By definition, (1) implies (2).

To show that (2) implies (3), let $f$ be a local minimizer for
$\operatorname{Dir}(f)$ within $[f]$; we wish to show $f$ is harmonic. One of
the first results in calculus of variations is that $f$ is constant-
derivative. So we only need to show the triangle inequalities. Let $v$ be a
unmarked vertex of $G$ of valence $k$, and let $d_{1},\dots,d_{k}$ be the non-
zero directions of $K$ at $f(v)$. For small $\varepsilon>0$, let
$f_{i,\varepsilon}$ be $f$ modified by moving $f(v)$ a distance $\varepsilon$
in the direction $d_{i}$, extended to the edges so that $f_{i,\varepsilon}$ is
still constant-derivative. By hypothesis
$\operatorname{Dir}(f)\leq\operatorname{Dir}(f_{i,\varepsilon})$. We have

$\operatorname{Dir}(f_{i,\varepsilon})=\operatorname{Dir}(f)+\sum_{d\in
f^{-1}(d_{i})}-2\varepsilon\lvert f^{\prime}(d)\rvert+\sum_{\mathstrut j\neq
i}\,\sum_{d\in f^{-1}(d_{j})}2\varepsilon\lvert
f^{\prime}(d)\rvert+\\!\sum_{d\text{ direction at
}v}\\!\varepsilon^{2}/\alpha(d).$

To be a local minimum, we must have for each $i$

$\frac{d}{d\varepsilon}\bigl{(}\operatorname{Dir}(f_{i,\varepsilon})\bigr{)}\Big{|}_{\varepsilon=0}\geq
0.$

This gives the $i$’th triangle inequality at $v$, so by Proposition 5.2, $f$
is harmonic.

To see that (3) implies (4), suppose that $f$ is harmonic. Then $f\circ\iota$
is taut and therefore energy-minimizing. Furthermore,

$\displaystyle\operatorname{EL}(\iota)$
$\displaystyle=\sum_{e\in\operatorname{Edge}(\Gamma)}\alpha(e)\lvert
f^{\prime}(e)\rvert^{2}=\operatorname{Dir}(f)$
$\displaystyle\ell(f\circ\iota)$
$\displaystyle=\sum_{e\in\operatorname{Edge}(\Gamma)}\lvert
f^{\prime}(e)\rvert\,\ell(f(e))=\operatorname{Dir}(f),$

so the energies are multiplicative, as desired.

Proposition 3.16 tells us that (4) implies (5).

Lemma 1.30 tells us that (4) or (5) implies (1).

Finally, to prove existence, let $g\in\operatorname{PL}^{*}[f]$ be any
constant-derivative map. Then
$\operatorname{Dir}[f]\leq\operatorname{Dir}(g)$. For each edge $e$, this
gives an upper bound on possible values of $\lvert f^{\prime}(e)\rvert$ for
any minimizer; let $D$ be a bound for all edges. Then $\operatorname{Dir}$ is
a continuous function on the compact complex $\operatorname{PL}^{*}[f]_{\leq
D}$, and therefore has a global minimum, which is harmonic. ∎

###  5.2. Harmonic maps to weak graphs

As with Lipschitz energy, we need a generalization of Theorem 5 to allow the
target to be a weak length graph.

######  Definition 5.3.

Let $(\widetilde{f},f)\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ be weak map between marked weak graphs, and
suppose there is a weight structure $w_{1}$ on $\Gamma_{1}$. Then $f$ is
_taut_ if there is a local lift $\widetilde{f}^{\prime}$ of $f$ so that
$\widetilde{f}^{\prime}$ is taut.

(Recall that in a weak map $(\widetilde{f},f)$, the local lift $\widetilde{f}$
is only defined up to local homotopy.)

######  Definition 5.4.

Let $G=(\Gamma,\alpha)$ be a marked elastic graph and let $K$ be a marked weak
length graph. We say that a weak map $(\widetilde{f},f)\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to K$ is _harmonic_ if it is constant-derivative and the weak map
$W_{f}\to K$ from the tension-weighted graph is taut.

We do not allow $G$ to be a weak graph. The definition could be extended to
this case with some more work (since when $e$ is a null edge, $\lvert
f^{\prime}(e)\rvert$ is not defined), but we will not need it.

######  Theorem 5′.

Let $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to K$ be a homotopy class of maps from a marked elastic graph to a
marked weak length graph. Then there is a harmonic weak map in $[f]$.
Furthermore, the following conditions are equivalent.

  1. (1)

The weak map $f$ is a global minimum for $\operatorname{Dir}$.

  2. (2)

The weak map $f$ is a local minimum for $\operatorname{Dir}$.

  3. (3)

The weak map $f$ is harmonic.

  4. (4)

There is a weighted curve $(C,c)$ on $G$ that forms a tight sequence

$C\overset{c}{\longrightarrow}G\overset{f}{\longrightarrow}K.$

###### Proof.

The most significant change from the proof of Theorem 5 is the proof that (2)
implies (3), which we now do. Let
$(\widetilde{g},g)\in\operatorname{PL}^{*}[f]$, and suppose that $g$ is not
harmonic in the sense of Definition 5.4. Then we will find a local
modification that reduces $\operatorname{Dir}(g)$. The possible local
modifications are more complicated than in the earlier proof, so we will use
the technology of taut maps from Section 3.

Fix $\varepsilon$ sufficiently small (to be specified). For $v$ a vertex of
$G$, let $N_{v}^{*}\subset K^{*}$ be the $\varepsilon$-neighborhood of $f(v)$.
We assume that $\varepsilon$ is small enough so that the $N_{v}^{*}$ are
disjoint regular neighborhoods. Let $N^{*}=\bigcup_{v}N_{v}^{*}$,
$N_{v}=\kappa^{-1}(N_{v}^{*})\subset K$, $N=\bigcup_{v}N_{v}$,
$M_{v}=g^{-1}(N_{v}^{*})\subset G$, and $M=\bigcup_{v}M_{v}$. We will use $M$
and $N$ for our neighborhoods in the definition of a weak map. On the
restriction of $\widetilde{g}$ to each neighborhood, set up a marked local
model, as in Definition 3.27. Choose $\widetilde{g}$ so each local model is
taut. By assumption, $\widetilde{g}$ is not taut everywhere on $K$. The
failure to be taut can only happen on $\partial N$. Let $y\in\partial N_{v}$
be one point where $\widetilde{g}$ is not locally taut, and let $Z$ be
$\widetilde{g}^{-1}(y)$, minus any isolated points in the middle of edges.

The edges incident to $Z$ can be divided into “inside” edges, those that
proceed into $N_{v}$, and “outside” edges, those that proceed away from
$N_{v}$. (For simplicity of notation assume that no edge has both ends
incident to $Z$.) Since $\widetilde{g}$ is not locally taut at $y$, the total
tension of the inside edges is not equal to the total tension of the outside
edges. We must have

(5.5) $\sum_{e\text{ inside}}\lvert g^{\prime}(e)\rvert<\sum_{e\text{
outside}}\lvert g^{\prime}(e)\rvert,$

as $\widetilde{g}$ restricted to $M_{v}$ is taut.

Let $(\widetilde{h},h)\in\operatorname{PL}^{*}[f]$ be the small modification
of $(\widetilde{g},g)$ so that $h$ maps each vertex in $Z$ to $y$ and agrees
with $g$ on all other vertices. In $h$ the length of the image of each inside
edge was increased by $\varepsilon$, and the length of the image of each
outside edge was decreased by $\varepsilon$. Then

$\displaystyle\operatorname{Dir}(h)-\operatorname{Dir}(g)$
$\displaystyle=\sum_{e\text{
inside}}\frac{\ell(g(e))\varepsilon+\varepsilon^{2}}{\alpha(e)}+\sum_{e\text{
outside}}\frac{-\ell(g(e))\varepsilon+\varepsilon^{2}}{\alpha(e)}$
$\displaystyle=\varepsilon\biggl{(}\sum_{e\text{ inside}}\lvert
f^{\prime}(e)\rvert-\sum_{e\text{ outside}}\lvert
f^{\prime}(e)\rvert\biggr{)}+O(\varepsilon^{2}),$

which is negative for $\varepsilon$ sufficiently small by Equation (5.5). Thus
$\operatorname{Dir}(h)<\operatorname{Dir}(g)$ and $f$ is not a local minimum
for $\operatorname{Dir}$.

The rest of the proof is almost unchanged: (1) implies (2) by definition, and
(4) implies (1) by properties of tight sequences. For (3) implies (4), if $f$
is harmonic, by definition of weak harmonic maps and Theorem 3 there is a
weighted multi-curve $(C,c)$ on $G$ so that $n_{c}=\lvert f^{\prime}\rvert$.
Then $C\overset{c}{\longrightarrow}G\overset{f}{\longrightarrow}K$ is tight.
Finally, existence follows from compactness of $\operatorname{PL}^{*}_{\leq
D}[f]$ (Lemma 4.9). ∎

We can improve the local lifts in a weak harmonic map a little.

######  Definition 5.6.

In a weak map $(\widetilde{f},f)\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$, we say that the local lift $\widetilde{f}$ is
_vertex-precise_ if it is strictly reduced and, for every vertex $v$ of
$\Gamma_{1}$, $\kappa_{2}(\widetilde{f}(v))=f(\kappa_{1}(v))$ on the nose
(with no need for homotopy).

######  Proposition 5.7.

If $(\widetilde{f},f)\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to K$ is a harmonic weak map, then $\widetilde{f}$ can be chosen to be
vertex-precise and taut as a map from $W_{f}$ to $K$.

###### Proof.

By definition of harmonic weak maps, we can find a taut initial lift
$\widetilde{f}$. If $\widetilde{f}$ does not map vertices to vertices, pick
some vertex $v$ so that $f(v)\neq\kappa(\widetilde{f}(v))$. Then
$\widetilde{f}(v)$ lies on an edge $e$ incident to $\kappa^{-1}(f(v))$. Since
$\widetilde{f}$ is taut, $n_{\widetilde{f}}$ is constant on $e$. We can thus
push $\widetilde{f}(v)$ into $\kappa^{-1}(f(v))$ without changing $f$ or
$n_{\widetilde{f}}$. Repeat until $\widetilde{f}$ maps vertices to vertices.
We can now straighten the edges (so that $\widetilde{f}$ is locally injective
or constant on each edge). Any remaining dead ends must be inside the null
sub-graphs and can be reduced away. ∎

###  5.3. Uniqueness and continuity

Harmonic maps are not in general unique in their homotopy class. For instance,
if the target length graph is a circle, then composing a harmonic map with any
rotation of the circle gives another harmonic map. However, the length of the
image of an edge in a harmonic map is unique. In fact, the lengths are unique
in a larger set.

######  Definition 5.8.

For $\Gamma$ a marked graph, $K$ a weak marked length graph, and
$[f]\nobreak\mskip 2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip
6.0mu plus 1.0mu\Gamma\to K$ a homotopy class of maps, a _relaxed map_ $r$
with respect to $[f]$ is an assignment of a length $r(e)$ to each edge $e$ of
$\Gamma$, so that, for any taut weighted marked multi-curve $(C,c)$ on
$\Gamma$,

(5.9) $\sum_{e\in\operatorname{Edge}(\Gamma)}n_{c}(e)r(e)\geq\ell[f\circ c].$

A relaxed map $r$ naturally gives a weak length metric on $\Gamma$. Let
$\operatorname{Rlx}[f]\subset\mathcal{L}(\Gamma)$ be the set of relaxed maps.
We write $\operatorname{Rlx}_{\ell}[f]$ if we need to make precise the
dependence on $\ell\in\mathcal{L}(K)$.

Although a relaxed map is not, in fact, any sort of map, the next three lemmas
show how relaxed maps are related to actual maps.

######  Lemma 5.10.

If $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ is a homotopy class,
$r\in\mathcal{L}(\Gamma_{1})$, and $\ell\in\mathcal{L}(\Gamma_{2})$, then
$r\in\operatorname{Rlx}_{\ell}[f]$ iff there is a map $g\in[f]$ with
$\operatorname{Lip}^{r}_{\ell}(g)\leq 1$.

###### Proof.

This is Theorem 4′. ∎

######  Lemma 5.11.

If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma\to K$ is a PL map, then
$f^{*}\ell\in\operatorname{Rlx}_{\ell}[f]$.

###### Proof.

By definition, $\operatorname{Lip}^{f^{*}\ell}_{\ell}(f)=1$. Apply Lemma 5.10.
∎

######  Lemma 5.12.

If $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma\to K$ is a homotopy class of maps from a marked graph $\Gamma$ to
a non-trivial weak marked length graph $K$ and $r\in\operatorname{Rlx}[f]$,
then there is a PL map $g\in[f]$ so that $r=g^{*}\ell$.

###### Proof.

Lemma 5.10 gives a PL map $g_{0}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu(\Gamma,r)\to K$ in $[f]$ with $\operatorname{Lip}(g_{0})\leq 1$. That
is, $\ell(g_{0}(e))\leq r(e)$ for each edge $e$ of $\Gamma$. Define $g$ by
modifying $g_{0}$: for each edge $e$ on which $\ell(g_{0}(e))<r(e)$, make the
length of the image of $e$ longer by introducing some zigzag folds. ∎

######  Lemma 5.13.

Definition 5.8 does not change if we let $(C,c)$ be

  1. (1)

a marked weighted train track,

  2. (2)

a marked weighted multi-curve (as in Definition 5.8),

  3. (3)

a marked curve with weight $1$, or

  4. (4)

a marked curve with weight $1$ that crosses each edge at most twice.

###### Proof.

The types of curve-like objects are progressively more restrictive, so we need
to show that the existence of a structure of one type violating Equation (5.9)
implies the next. Condition (1) implies condition (2) by Proposition 3.16.
Condition (2) implies condition (3) by additivity Eq. (5.9) over connected
components. Condition (3) implies condition (4) by Lemma 5.10 and Theorem 4′
or, more simply, by taking any curve, looking for a maximal segment with no
repeated oriented edges, doing cut-and-paste if necessary, and then using
additivity over the connected components. ∎

######  Lemma 5.14.

For $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ a homotopy class of maps between marked graphs
and $\ell\in\mathcal{L}(\Gamma_{2})$, $\operatorname{Rlx}_{\ell}[f]$ is a
closed, non-compact, convex polytope defined by finitely many inequalities,
each inequality depending linearly on $\ell$.

###### Proof.

This follows from condition (4) of Lemma 5.13, as there are only finitely many
multi-curves crossing each edge at most twice, and Equation (5.9) cuts out a
closed half-space for each such multi-curve. Scaling a relaxed map by a factor
$\lambda>1$ gives another relaxed map, so $\operatorname{Rlx}[f]$ is not
compact. ∎

If $r\in\operatorname{Rlx}[f]$ is a relaxed map where the domain is an elastic
graph $(\Gamma,\alpha)$, we can define the Dirichlet energy of $r$:

(5.15)
$\operatorname{Dir}^{\alpha}(r)\coloneqq\sum_{e\in\operatorname{Edge}(\Gamma)}\frac{r(e)^{2}}{\alpha(e)}.$

In fact, Equation (5.15) makes sense for any $r\in\mathcal{L}(\Gamma)$.

We can now give the uniqueness statement.

######  Proposition 5.16.

If $f\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to K$ is a harmonic map from a marked elastic graph to a weak marked
length graph, then $f^{*}\ell$ uniquely minimizes Dirichlet energy on
$\operatorname{Rlx}_{\ell}[f]$.

###### Proof.

Let $G=(\Gamma,\alpha)$. The function $\operatorname{Dir}^{\alpha}$ is
strictly convex on $\mathcal{L}(\Gamma)$, and its sub-level sets are compact.
As such, $\operatorname{Dir}^{\alpha}$ achieves a unique minimum on the closed
convex set $\operatorname{Rlx}[f]$. Since $f$ was harmonic, it minimizes
$\operatorname{Dir}(f)$ in $[f]$; since every point in $\operatorname{Rlx}[f]$
gives the lengths of an actual map in $[f]$, the minimizer in
$\operatorname{Rlx}[f]$ must be $f^{*}\ell$. ∎

In light of Proposition 5.16, we can think of Dirichlet energy and the length
of edges of the harmonic minimizer as functions on $\mathcal{L}(K)$.

######  Definition 5.17.

For $[f]$ a homotopy class of maps from a marked elastic graph
$(\Gamma_{1},\alpha)$ to a marked graph $\Gamma_{2}$, define

$\displaystyle\operatorname{Dir}_{[f]}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\mathcal{L}(\Gamma_{2})$ $\displaystyle\to\mathbb{R}$ $\displaystyle
H_{[f]}\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\mathcal{L}(\Gamma_{2})$ $\displaystyle\to\mathcal{L}(\Gamma_{1})$

by setting $\operatorname{Dir}_{[f]}(\ell)$ to
$\operatorname{Dir}^{\alpha}_{\ell}[f]$ and $H_{[f]}(\ell)$ to the relaxed map
in $\operatorname{Rlx}_{\ell}[f]$ minimizing $\operatorname{Dir}^{\alpha}$.

######  Proposition 5.18.

Let $[f]\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG\to\Gamma_{2}$ be a homotopy class of maps from a marked elastic graph
to a marked graph. Then $\operatorname{Dir}_{[f]}$ and $H_{[f]}$ are
continuous functions on $\mathcal{L}(\Gamma_{2})$, with
$\operatorname{Dir}_{[f]}$ piecewise-quadratic and $H_{[f]}$ piecewise-linear.

###### Proof.

As $\ell\in\mathcal{L}(\Gamma_{2})$ varies, the closed convex set
$\operatorname{Rlx}_{\ell}[f]$ varies continuously by Lemma 5.14. Since
$\operatorname{Dir}^{\alpha}$ is strictly convex, both the value and location
of the minimum of $\operatorname{Dir}^{\alpha}$ on
$\operatorname{Rlx}_{\ell}[f]$ depend continuously on $\ell$.

Furthermore, since $\operatorname{Dir}^{\alpha}$ is quadratic on
$\mathcal{L}(\Gamma)$ and $\operatorname{Rlx}_{\ell}[f]$ depends piecewise-
linearly on $\ell$, the value of the minimum of $\operatorname{Dir}^{\alpha}$
on $\operatorname{Rlx}_{\ell}[f]$ is a piecewise-quadratic function of $\ell$
and the location of the minimum is a piecewise-linear function of $\ell$. (The
particular quadratic or linear function depends on the face of
$\operatorname{Rlx}_{\ell}[f]$ containing the minimum.) ∎

See also Remark 6.37.

######  Remark 5.19.

An alternate way to see that $\operatorname{Dir}_{[f]}$ is piecewise-quadratic
and that $H_{[f]}$ is piecewise-linear is to note that they are respectively
quadratic and linear for a fixed combinatorial type of a harmonic
representative, and only finitely many combinatorial types of maps appear by
Theorem 5′ and Proposition 3.35. The combinatorial type is related to the face
of $\operatorname{Rlx}_{\ell}[f]$ containing $H_{[f]}(\ell)$.

##  6\. Minimizing embedding energy

###  6.1. Characterizing minimizers: $\lambda$-filling maps

We now turn to Theorem 1, starting with a characterization of which maps can
appear as minimizers of $\operatorname{Emb}[\phi]$.

######  Definition 6.1.

A _strip graph_ $S=(\Gamma,w,\ell)$ is a marked graph $\Gamma$ with balanced
weights $w\in\mathcal{W}(\Gamma)$ and lengths $\ell\in\mathcal{L}(\Gamma)$, so
that $w(e)\neq 0$ iff $\ell(e)\neq 0$. The strip graph is _positive_ if all
lengths and weights are positive, and is _balanced_ if $w$ is balanced
(Definition 3.14).

There is an associated marked weighted graph $W_{S}=(\Gamma,w)$ and weak
marked length graph $K_{S}=(\Gamma,\ell)$. We say that $S$ is _compatible_
with an elastic graph $G_{S}=(\Gamma,\alpha)$ if $\ell(e)=w(e)\alpha(e)$ for
each edge $e$. (If $S$ is positive, then $G_{S}$ is unique.) A strip graph
also has an _area_

$\operatorname{Area}(S)\coloneqq\sum_{e\in\operatorname{Edge}(\Gamma)}\ell(e)w(e).$

######  Lemma 6.2.

A balanced strip graph $S$ gives a tight sequence of maps

$W_{S}\overset{}{\longrightarrow}G_{S}\overset{}{\longrightarrow}K_{S}\overset{}{\longrightarrow}K^{*}_{S}.$

(Recall from Definition 4.1 that $K_{S}^{*}$ is $K_{S}$ with the null edges
collapsed.)

###### Proof.

The fact that the map $W_{S}\to K_{S}$ is taut (hence energy-minimizing) is
the condition that $w$ is balanced. The map $W_{s}\to K_{S}^{*}$ is then taut
by Lemmas 3.37 and 3.40. We also have

$\displaystyle\ell(W_{S}\to K_{S}^{*})=\operatorname{EL}(W_{S}\to
G_{S})=\operatorname{Dir}(G_{S}\to K_{S})$
$\displaystyle=\operatorname{Area}(S)$
$\displaystyle\operatorname{Lip}(K_{S}\to K^{*}_{S})$ $\displaystyle=1,$

so the energies are multiplicative, as desired. ∎

######  Definition 6.3.

Let $S_{1}=(\Gamma_{1},w_{1},\ell_{1})$ and
$S_{2}=(\Gamma_{2},w_{2},\ell_{2})$ be two marked balanced strip graphs. Write
$G_{1}$ for $G_{S_{1}}$, etc. (This may involve choices.) For a PL map
$\phi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$, we also write, e.g., $\phi^{W}_{G}$ for the
associated map from the weighted graph $(\Gamma_{1},w_{1})$ to the elastic
graph $(\Gamma_{2},\ell_{2}/w_{2})$.

Then if $\lambda>0$ is a real number and $S_{2}$ is positive,
$\phi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0mu\Gamma_{1}\to\Gamma_{2}$ is _$\lambda$ -filling_ if

  1. (1)

$\phi^{W}$ is taut;

  2. (2)

lengths are preserved: $\phi^{K}_{K}$ is a local isometry; and

  3. (3)

weights are scaled by a factor of $\lambda$: for every regular value
$y\in\Gamma_{2}$,

(6.4) $\sum_{x\in\phi^{-1}(y)}w_{1}(x)=\lambda w_{2}(y).$

In other words, $n_{\phi}^{w_{1}}=\lambda w_{2}$ and in particular
$\operatorname{WR}(\phi^{W}_{W})=\lambda$.

We also say the associated map $\phi^{G}_{G}$ between marked elastic graphs is
$\lambda$-filling.

######  Lemma 6.5.

Suppose $\phi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muS_{1}\to S_{2}$ is a $\lambda$-filling map. Then
$\operatorname{Fill}_{\phi^{G}_{G}}$ is identically equal to $\lambda$. In
particular, $\operatorname{Emb}(\phi^{G}_{G})=\lambda$.

###### Proof.

Since $\phi$ is constant on the $0$-length edges of $S_{1}$, we may assume
that $S_{1}$ is positive as well. Since $\phi^{K}_{K}$ is length-preserving
and $\alpha_{i}(e)=\ell_{i}(e)/w_{i}(e)$ for $i=1,2$ (when defined), it
follows that, for regular points $x\in G_{1}$,

$\left\lvert\bigl{(}\phi^{G}_{G}\bigr{)}^{\prime}(x)\right\lvert=w_{1}(x)/w_{2}(\phi(x)).$

The result follows from Equation (6.4). ∎

######  Lemma 6.6.

A $\lambda$-filling map $\phi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muS_{1}\to S_{2}$ gives a tight sequence of maps

$W_{1}\overset{}{\longrightarrow}G_{1}\overset{\phi^{G}_{G}}{\longrightarrow}G_{2}\overset{}{\longrightarrow}K_{2}.$

###### Proof.

The composite $W_{1}\to K_{2}$ is taut by assumption. The energies of the
various maps are

$\displaystyle\operatorname{EL}(W_{1}\longrightarrow G_{1})$
$\displaystyle=\operatorname{Area}(S_{1})$
$\displaystyle\operatorname{Emb}(G_{1}\overset{\phi^{G}_{G}}{\longrightarrow}G_{2})$
$\displaystyle=\lambda$ $\displaystyle\operatorname{Dir}(G_{2}\longrightarrow
K_{2})$
$\displaystyle=\operatorname{Area}(S_{2})=\operatorname{Area}(S_{1})/\lambda$
$\displaystyle\ell(W_{1}\longrightarrow K_{2})$
$\displaystyle=\operatorname{Area}(S_{1}).$

This is multiplicative, as desired. ∎

######  Proposition 6.7.

Let $\phi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ be a map between marked elastic graphs $G_{1}$ and
$G_{2}$. If there is a $\lambda$-filling map $\psi\in[\phi]$, then
$\operatorname{Emb}[\phi]=\operatorname{SF}_{\operatorname{Dir}}[\phi]=\operatorname{SF}_{\operatorname{EL}}[\phi]=\operatorname{Emb}(\psi)=\lambda$.

###### Proof.

Immediate from Lemmas 6.5, 6.6 and 1.30. ∎

Thus, $\lambda$-filling maps are optimizers for $\operatorname{Emb}$. If there
were always a $\lambda$-filling map in $[\phi]$, then we would be done with
Theorem 1. Unfortunately this is not true.

######  Example 6.8.

Let $G_{1}$ and $G_{2}$ both be the join of two circles, with elastic
constants $(2,2)$ and $(1,4)$, respectively, and let $\phi\nobreak\mskip
2.0mu\mathpunct{}\nonscript\mkern-3.0mu{:}\allowbreak\mskip 6.0mu plus
1.0muG_{1}\to G_{2}$ be the constant-derivative map which is the identity on
$\pi_{1}$ and maps the vertex to the vertex:

$\vbox{\hbox{$\includegraphics[trim=-1.00374pt -1.00374pt -1.00374pt
-1.00374pt]{graphs-61}$}}\quad\overset{\phi}{\longrightarrow}\quad\vbox{\hbox{$\includegraphics[trim=-1.00374pt
-1.00374pt -1.00374pt -1.00374pt]{graphs-62}$}}.$

Then $\operatorname{Emb}(\phi)=2$. Furthermore,
$\operatorname{SF}_{\operatorname{EL}}[\phi]\geq 2$, by considering the right-
hand loop of $G_{1}$. Thus
$\operatorname{Emb}[\phi]=\operatorname{Emb}(\phi)=\operatorname{SF}_{\operatorname{EL}}[\phi]=2$.
There is no $\lambda$-filling map in $[\phi]$.

######  Definition 6.9.

Let $S_{1}=(\Gamma_{1},w_{1},\ell_{1})$ and