\documentclass[ALCO,ThmDefs,Unicode,epreuves]{cedram} \OneNumberAllTheorems \usepackage{tikz} \providecommand{\dobbensort}[1]{} \begin{DefTralics} \newcommand{\dobbensort}[1]{} \end{DefTralics} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% New definitions (macros, mostly for mathematics) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\Z}{\ensuremath{\mathbb{Z}}} \newcommand{\R}{\ensuremath{\mathbb{R}}} \newcommand{\transp}{\mathsf{T}} \newcommand{\one}{\ensuremath{\mathbf{1}}} \DeclareMathOperator{\tw}{tw} \DeclareMathOperator{\Div}{Div} \DeclareMathOperator{\Rat}{Rat} \DeclareMathOperator{\Prin}{Prin} \DeclareMathOperator{\Col}{Col} \DeclareMathOperator{\todiv}{div} \DeclareMathOperator{\dgon}{dgon} \DeclareMathOperator{\sgon}{sgon} \DeclareMathOperator{\supp}{supp} \DeclareMathOperator{\rank}{rank} \newcommand*{\B}{\mathcal{B}} %\newcommand*{\order}[1]{\left|\left|#1\right|\right|} \newcommand*{\order}[1]{\left\Vert#1\right\Vert} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% TikZ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\hittingsetTikZ} {\begin{tikzpicture}[punt/.style={draw,circle,inner sep=.9pt}, grootpunt/.style={fill,circle,inner sep=1.3pt}] \draw[rounded corners=5pt,fill=green!30!gray!6] (0,0) rectangle (5.5,3.5); \node[anchor=base west] at (0.1,3) {$U$}; \draw[rounded corners=5pt,fill=green!30!gray!6] (6,0) rectangle (11.5,3.5); \node[anchor=base east] at (11.4,3) {$V\setminus U$}; \draw[rounded corners=5pt,fill=purple!60!gray!10] (4.5,0.1) rectangle (5.3,3.4); \node[anchor=base] at (4.9,0.3) {$X$}; \draw[rounded corners=5pt,fill=purple!60!gray!10] (6.2,0.1) rectangle (7,3.4); \node[anchor=base] at (6.6,0.3) {$Y$}; \draw[fill=blue,fill opacity=0.05] (3.5,1.5) ellipse (16mm and 9mm); \node at (2.6,1.9) {$B'$}; \draw[fill=blue,fill opacity=0.05] (8.3,1.7) ellipse (19mm and 9mm); \node at (9.2,2.1) {$B$}; \node[grootpunt] (A1) at (4.9,3) {}; \node[punt] (B1) at (6.6,3) {}; \draw (A1) -- (B1); \node[grootpunt] (B2) at (6.6,2.6) {}; \node[punt] (A2) at (4.7,1.9) {}; \draw (B2) -- (A2); \node[grootpunt] (B3) at (6.8,2) {}; \node[punt] (A3) at (4.9,1.55) {}; \draw (B3) -- (A3); \node[grootpunt] (A4) at (4.9,2.5) {}; \node[punt] (B4) at (6.7,1.5) {}; \draw (A4) -- (B4); \node[grootpunt,label=below:$s$,outer sep=-1pt] (s) at (4.65,1.3) {}; \node[grootpunt] (B5) at (6.6,1.0) {}; \draw (s) -- (B5); \end{tikzpicture}} \newcommand{\PetersenTikZa} {\begin{tikzpicture}[x=0.8cm,y=0.8cm] \tikzstyle{vertex}=[circle, draw, fill=white, inner sep=0pt, minimum width=12pt, font=\footnotesize] \tikzstyle{edge} = [] \tikzstyle{fedge} = [line width=15pt, color=black!30!white, shorten <=-8pt, shorten >=-8pt, line cap=round] \node[vertex] (a) at (0,-1) {$6$}; \node[vertex] (b) at (0.95,-0.31) {$7$}; \node[vertex] (c) at (0.59,0.81) {$8$}; \node[vertex] (d) at (-0.59,0.81) {$9$}; \node[vertex] (e) at (-0.95,-0.31) {$10$}; \node[vertex] (A) at (0,-2) {$1$}; \node[vertex] (B) at (1.9,-0.62) {$2$}; \node[vertex] (C) at (1.18,1.62) {$3$}; \node[vertex] (D) at (-1.18,1.62) {$4$}; \node[vertex] (E) at (-1.9,-0.62) {$5$}; \draw[fedge] (a)--(A); \draw[fedge] (b)--(B); \draw[fedge] (c)--(C); \draw[fedge] (d)--(D); \draw[fedge] (e)--(E); \node[vertex] (a) at (0,-1) {$6$}; \node[vertex] (b) at (0.95,-0.31) {$7$}; \node[vertex] (c) at (0.59,0.81) {$8$}; \node[vertex] (d) at (-0.59,0.81) {$9$}; \node[vertex] (e) at (-0.95,-0.31) {$10$}; \node[vertex] (A) at (0,-2) {$1$}; \node[vertex] (B) at (1.9,-0.62) {$2$}; \node[vertex] (C) at (1.18,1.62) {$3$}; \node[vertex] (D) at (-1.18,1.62) {$4$}; \node[vertex] (E) at (-1.9,-0.62) {$5$}; \draw[edge] (a)--(A); \draw[edge] (b)--(B); \draw[edge] (c)--(C); \draw[edge] (d)--(D); \draw[edge] (e)--(E); \draw[edge] (a)--(c)--(e)--(b)--(d)--(a); \draw[edge] (A)--(B)--(C)--(D)--(E)--(A); \end{tikzpicture}} \newcommand{\PetersenTikZb}{ \begin{tikzpicture}[x=0.8cm,y=0.8cm] \tikzstyle{vertex}=[circle, draw, fill=white, inner sep=0pt, minimum width=12pt, font=\footnotesize] \tikzstyle{rvertex}=[circle, draw, fill=white!60!red, inner sep=0pt, minimum width=12pt, font=\footnotesize] \tikzstyle{edge} = [] \tikzstyle{fedge} = [line width=15pt, color=black!30!white, shorten <=-8pt, shorten >=-8pt, line cap=round] \node[rvertex] (a) at (0,-1) {$6$}; \node[rvertex] (b) at (0.95,-0.31) {$7$}; \node[vertex] (c) at (0.59,0.81) {$8$}; \node[vertex] (d) at (-0.59,0.81) {$9$}; \node[vertex] (e) at (-0.95,-0.31) {$10$}; \node[vertex] (A) at (0,-2) {$1$}; \node[vertex] (B) at (1.9,-0.62) {$2$}; \node[rvertex] (C) at (1.18,1.62) {$3$}; \node[vertex] (D) at (-1.18,1.62) {$4$}; \node[rvertex] (E) at (-1.9,-0.62) {$5$}; \draw[edge] (a)--(A); \draw[edge] (b)--(B); \draw[edge] (c)--(C); \draw[edge] (d)--(D); \draw[edge] (e)--(E); \draw[edge] (a)--(c)--(e)--(b)--(d)--(a); \draw[edge] (A)--(B)--(C)--(D)--(E)--(A); \end{tikzpicture}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%% a placer avant \begin{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand*{\mk}{\mkern -1mu} \newcommand*{\Mk}{\mkern -2mu} \newcommand*{\mK}{\mkern 1mu} \newcommand*{\MK}{\mkern 2mu} \hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red} \newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}} \newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}} \newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}} \newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% Auteur %%% \author{\firstname{Josse} \lastname{van Dobben de Bruyn}} \address{Mathematical Institute\\ Leiden University\\ P.O.~Box 9512\\ 2300 RA Leiden, The Netherlands} \curraddr{Delft Institute of Applied Mathematics\\ Delft University of Technology\\ Van Mourik Broekmanweg 6\\ 2628 XE Delft, The Netherlands} \email{J.vanDobbendeBruyn@tudelft.nl} %%%2 \author{\firstname{Dion} \lastname{Gijswijt}} \address{Delft Institute of Applied Mathematics\\ Delft University of Technology\\ Van Mourik Broekmanweg 6\\ 2628 XE Delft, The Netherlands} \email{D.C.Gijswijt@tudelft.nl} \urladdr{https://homepage.tudelft.nl/64a8q/} %%%%% Sujet \subjclass{05C57, 05C83, 14T05, 14H51} \keywords{Gonality, treewidth, tropical curve, metric graph.} %%%%% Gestion \DOI{10.5802/alco.124} \datereceived{2019-09-12} \daterevised{2020-04-11} \dateaccepted{2020-04-12} %%%%% Titre et résumé \title[Treewidth is a lower bound on graph gonality]{Treewidth is a lower bound on graph~gonality} \begin{abstract} We prove that the (divisorial) gonality of a finite connected graph is lower bounded by its treewidth. Graphs for which equality holds include the grid graphs and the complete multipartite graphs. We prove that the treewidth lower bound also holds for \emph{metric graphs} (\emph{tropical curves}) by constructing for any positive rank divisor on a metric graph a positive rank divisor of the same degree on a subdivision of the underlying combinatorial graph. Finally, we show that the treewidth lower bound also holds for a related notion of gonality defined by Caporaso and for stable gonality as introduced by Cornelissen et al. \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% Actual document starts HERE: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \maketitle \section{Introduction} In~\cite{BakerNorine2007}, Baker and Norine developed a theory of divisors on finite graphs analogous to divisor theory for Riemann surfaces. In particular, they stated and proved a graph theoretical analogue of the classical Riemann--Roch theorem. An important parameter of a Riemann surface is its gonality: the minimum degree of a holomorphic map to the Riemann sphere. Alternatively, the gonality can be defined as the minimum degree of a positive rank divisor. This second definition has a direct combinatorial analogue called the \emph{(divisorial) gonality}, $\dgon(G)$, of a graph~$G$. By Baker's Specialization Lemma, the gonality of a smooth algebraic curve is bounded from below by the gonality of (a subdivision of) the dual graph associated to the curve (see Corollary~3.2 in~\cite{Baker2008}). Hence, lower bounds for graph gonality, such as the treewidth bound proved here, can be used to obtain results for algebraic curves. See~\cite{Baker2008, CornelissenKatoKool2012, HKN} for background on the interplay between divisors on graphs, curves and tropical curves. As observed in~\cite{BakerNorine2007}, there is also a close connection between divisor theory on graphs and the \emph{chip-firing game} of Bj{\"o}rner-Lov{\'a}sz-Shor~\cite{BLS1991} (see also~\cite{Merino} for the connection to the Abelian sandpile model and Biggs' dollar game~\cite{Biggs}). The graph parameter~$\dgon(G)$ can be described in terms of a chip-firing game as follows (we will give a more formal definition later on). At any stage, we have a chip configuration consisting of a nonnegative number of chips at each vertex of~$G$. We can move to a different chip configuration by \emph{firing} a subset~$U\subseteq V(G)$ of vertices: for each edge~$uv$ with $u\in U$ and $v\not\in U$ we remove one chip from~$u$ and add one chip to~$v$. Firing a subset~$U$ is only allowed if every vertex~$u\in U$ has at least as many chips as it has edges to vertices outside $U$ (otherwise it would be left with a negative number of chips). A chip configuration is \emph{winning} if for every vertex~$v$ there is a sequence of allowed moves that results in a configuration with at least one chip on~$v$. The gonality $\dgon(G)$ of~$G$ is the smallest number of chips in a winning chip configuration. Since the gonality of a graph is the sum of the gonalities of the connected components, we will restrict attention to connected graphs. It is well-known that the connected graphs of gonality~$1$ are precisely the trees. In fact it is easy to see that the gonality is invariant under adding leaves (vertices of degree~$1$). The graphs of gonality~$2$ were characterized by Chan~\cite{Chan}. Their result is stated in the more general context of metric graphs. Specialising to divisorial gonality on graphs, it implies \begin{theo*}[{Implied by~\cite[Theorem~1.3]{Chan}}] Let $G$ be a connected graph with no vertices of degree less than~$2$. Then $\dgon(G)=2$ if and only if there is a graph automorphism~$i:G\to G$ of order~$2$ such that $G/i$ is a tree. \end{theo*} No characterisation for graphs of gonality~$3$ is known. A trivial upper bound is $\dgon(G)\leq |V|$, which can be strengthened to $\dgon(G)\leq |V|-\alpha(G)$ for simple graphs, where $\alpha(G)$ denotes the stability number of~$G$. An upper bound $\dgon(G)\leq \frac{|E|-|V|+4}{2}$, matching the classical Brill--Noether bound, was conjectured by Baker~\cite[Conjecture~3.10]{Baker2008}. In this paper we prove a lower bound for the gonality. Our main result is the following theorem that was conjectured in~\cite{vanDobbendeBruyn2012}. \begin{theorem} Let $G$ be a connected graph with treewidth~$\tw(G)$ and gonality~$\dgon(G)$. Then $\tw(G)\leq \dgon(G)$. \end{theorem} Section~2 is devoted to preliminaries, including basic notation and terminology related to graphs, divisors and treewidth. In Section~3, we state and prove the main theorem. In Section~4, we consider some families of graphs for which treewidth equals gonality. These include: trees, grids, and complete multipartite graphs. In Section~5, we briefly review divisor theory for \emph{metric} graphs. We show that the gonality of a metric graph is lower bounded by the gonality of a subdivision of the underlying graph. Hence, the treewidth is also a lower bound for metric graphs (tropical curves). In Section~6, we discuss some related notions of gonality defined in terms of harmonic morphisms, and show that there the treewidth is also a lower bound. \section{Preliminaries} The graphs in this paper will be finite and undirected (unless stated otherwise). We allow our graphs to have multiple (parallel) edges, but no loops. We will almost exclusively consider \emph{connected} graphs. For a graph~$G$, we denote by $V(G)$ and $E(G)$ the set of vertices and edges of~$G$, respectively. By an edge~$uv$, we mean an edge with ends $u$~and~$v$. For (not necessarily disjoint) subsets~$U,W\subseteq V(G)$, we denote by $E(U,W)$ the set of edges with an end in~$U$ and an end in~$W$. For vertices~$u$ and~$v$, we use the abbreviations $E(u,v)\coloneqq E(\{u\},\{v\})$ and $E(u)\coloneqq E(\{u\},V\setminus \{u\})$. The degree of a vertex~$v$ equals the number of edges with $v$ as an endpoint and is denoted by $d_G(v)\coloneqq |E(v)|$. For a subset~$U\subseteq V(G)$, we denote by $G[U]\coloneqq (U,E(U,U))$ the subgraph of~$G$ \emph{induced by~$U$}. That is, $G[U]$ is the graph with vertex set~$U$ and edge set consisting of the edges of~$G$ with both ends in~$U$. Let $G=(V,E)$ be a \emph{connected} graph. We can make $G$ into an \emph{oriented graph} by, for every edge~$e$, assigning one end to be the \emph{head} of~$e$ and the other end to be the \emph{tail} of~$e$. We view the edge~$e$ as oriented from its tail to its head. For a cycle~$C$ in~$G$, we then denote by $\chi_C\in \R^{E}$ the signed incidence vector defined by \begin{equation} \chi_C(e)=\begin{cases} 1& \text{if $e$ is traversed in forward direction by $C$,}\\ -1&\text{if $e$ is traversed in backward direction by $C$,}\\ 0&\text{otherwise.} \end{cases} \end{equation} Similarly, we write $\chi_P$ for the signed incidence vector of a path~$P$. The \emph{incidence matrix}~$M=M(G)\in \R^{V\times E}$ of~$G$ is defined by, for every~$v\in V$ and~$e\in E$, setting \begin{equation} M_{v,e}\coloneqq \begin{cases} 1&\text{if $v$ is the head of $e$,}\\ -1&\text{if $v$ is the tail of $e$,}\\ 0&\text{otherwise.} \end{cases} \end{equation} \noindent The matrix~$Q=Q(G)\coloneqq MM^\transp$ is the \emph{Laplacian} of~$G$ and it is independent of the chosen orientation. Indeed, for any two vertices~$u$ and~$v$, $Q_{vv}$ equals the degree of vertex~$v$ and $Q_{uv}$ equals~$-|E(u,v)|$. The \emph{cut lattice} of~$G$ is the set~$\Z^{E}\cap \Col(M^\transp)$ of integral vectors in the column space of the transpose of~$M$. The following two lemmas are well-known, and can be found in many books on algebraic graph theory (for example~\cite{GodsilRoyle2001}). For the benefit of the reader, we will give the short proofs. \begin{lemma}\label{clattice} Let $f\in \Z^{E}$. Then the following are equivalent: \begin{enumerate}[label=(\roman*)] \item\label{lemma2.1_i} $f$ is in the cut lattice of $G$, \item\label{lemma2.1_ii} $f^\transp\chi_C=0$ for every cycle $C$ in $G$, \item\label{lemma2.1_iii} $f=M^\transp x$ for some $x\in \Z^{V}$. \end{enumerate} \end{lemma} \begin{proof} The implication from~\ref{lemma2.1_iii} to~\ref{lemma2.1_i} is trivial. The implication from~\ref{lemma2.1_i} to~\ref{lemma2.1_ii} follows since $M\chi_C=0$ for every cycle~$C$. For the implication from~\ref{lemma2.1_ii} to~\ref{lemma2.1_iii}, let $f\in \Z^{E}$ satisfy the condition in~\ref{lemma2.1_ii}. Let $T$ be a spanning tree in~$G$ with root~$r$, and define $x\in \Z^V$ by $x(v)\coloneqq f^\transp\chi_{P_v}$, where $P_v$ is the path in~$T$ from~$r$ to~$v$. Now for every edge~$e=uv$ oriented from~$u$ to~$v$, we have $x(v)-x(u)=f(e)$. Hence, $f=M^\transp x$. \end{proof} \begin{lemma}\label{Laplacian} The null space of~$Q$ is spanned by the all-one vector~$\one$. \end{lemma} \begin{proof} Since the row sums of~$Q$ equal zero, it is clear that~$Q\one=0$. Conversely, let $x$ be in the null space of~$Q$ and suppose, for contradiction, that $x$ is not a multiple of~$\one$. Since $G$ is connected, we may choose $v\in V$ for which $x(v)$ is maximal and such that $v$ has a neighbour~$u$ with $x(u) < x(v)$. From~$Qx=0$ it follows that $d_G(v)x(v)=\sum_{w\in V\setminus\{v\}} |E(v,w)|\cdot x(w)$. On the other hand, \begin{equation*} \sum_{w\in V\setminus\{v\}}|E(v,w)|\cdot x(w)\ < \sum_{w\in V\setminus\{v\}}|E(v,w)|\cdot x(v)= d_G(v)x(v) \end{equation*} by our choice of~$v$. This is a contradiction. \end{proof} \subsection{Divisors on graphs} We will largely adopt notation from~\cite{BakerNorine2007}. Let $G=(V,E)$ be a connected graph. A vector~$D\in \Z^V$ is called a \emph{divisor} on~$G$. The set~$\Div(G)\coloneqq \Z^V$ denotes the set of all divisors on~$G$. For a divisor~$D\in \Div(G)$ we call $\deg(D)\coloneqq \sum_{v\in V}D(v)$ the \emph{degree} of~$D$. A divisor~$D$ is said to be \emph{effective} if it is nonnegative, that is, $D(v)\geq 0$ for all~$v\in V$. We denote by $\Div_+(G)$ the set of effective divisors on~$G$ and by $\Div_+^k(G)$ the set of effective divisors of degree~$k$. We denote by $\supp(D)\coloneqq \{v\in V\mid D(v)\neq 0\}$ the \emph{support} of~$D$. We call two divisors~$D$ and~$D'$ \emph{equivalent} and write $D\sim D'$ if there is an integer vector~$x\in \Z^V$ such that $D-D'=Q(G)x$. Clearly, this is indeed an equivalence relation. Observe that equivalent divisors have equal degree as $Q(G)$ has column sums equal to zero. We will often consider the situation where $x$ is the incidence vector of a subset~$U$ of~$V$, that is, $D'=D-Q(G)\one_U$. Observe that in this case \begin{equation} D'(v)=\begin{cases}D(v)-|E(\{v\},V\setminus U)|&\text{if $v\in U$},\\D(v)+|E(\{v\},U)|&\text{if $v\in V\setminus U$.}\end{cases} \end{equation} In particular, $D'(v)\leq D(v)$ if $v\in U$ and $D'(v)\geq D(v)$ if $v\in V\setminus U$. In terms of chip firing, we move one chip along each edge in the cut~$E(U,V\setminus U)$. The following lemma shows that for equivalent effective divisors~$D$ and~$D'$, we can obtain $D'$ from~$D$ by a sequence of steps of this form such that each intermediate divisor is effective as well. \begin{lemma}\label{chain} Let $D_0$ and~$D$ be equivalent effective divisors satisfying~$D \neq D_0$. There is a chain of sets~$\emptyset\subsetneq U_1\subseteq U_2\subseteq \cdots\subseteq U_k\subsetneq V$ such that $D_t\coloneqq D-Q(G)(\sum_{i=1}^t \one_{U_i})$ is effective for every~$t=1,\ldots,k$ and such that~$D_k=D$. Moreover, this chain is unique. \end{lemma} \begin{proof} Since~$D_0\sim D$, there exists an~$x\in \Z^V$ such that~$D_0-Q(G)x=D$. By Lemma~\ref{Laplacian}, $x$ is unique up to integral multiples of~$\one$. Hence, there is a unique such $x$ with the additional property that $x\geq 0$ and $\supp(x)\neq V$. Let $k\coloneqq \max\{x(v)\mid v\in V\}$ and define $U_i\coloneqq \{v\in V\mid x(v)\geq k-i+1\}$ for $i=1,\ldots, k$. We have $\emptyset\subsetneq U_1\subseteq U_2\subseteq \cdots\subseteq U_k\subsetneq V$ as required. Also, $\sum_{i=1}^k \one_{U_i}=x$ and hence $D_k=D_0-Q(G)x=D$. Consider any~$t\in \{1,\ldots, k-1\}$. To show effectiveness of~$D_t$, consider any~$v\in V$. If $v\not\in U_t$, then $D_0(v)\leq D_1(v)\leq \cdots\leq D_t(v)$, hence~$D_t(v)\geq 0$. If~$v\in U_t$, then $D_t(v)\geq D_{t+1}(v)\geq \cdots \geq D_k(v)$, hence~$D_t(v)\geq 0$. Uniqueness follows directly from the uniqueness of an~$x\in \Z^V$ for which $x\geq 0$, $\supp(x)\neq V$ and $D_0-Q(G)x=D$, in combination with the uniqueness of the decomposition~$x=\sum_{i=1}^k\one_{U_i}$ as a sum of characteristic vectors of a chain~$\emptyset\subsetneq U_1\subseteq U_2\subseteq \cdots\subseteq U_k\subsetneq V$. \end{proof} The \emph{rank} of a divisor~$D$ is defined as \begin{multline} \rank(D)\coloneqq \max\{k\mid \text{$D-D'$ is equivalent to an effective divisor}\\\text{ for every~$D'\in\Div_+^k$}\}. \end{multline} Observe that equivalent divisors have equal rank and that $\rank(D)\leq \deg(D)$. Following Baker~\cite{Baker2008}, we define the \emph{gonality} of~$G$ by \begin{equation} \dgon(G)\coloneqq \min\{k\mid \text{there is a divisor of degree~$k$ on~$G$ with positive rank}\}. \end{equation} An effective divisor~$D$ is called \emph{$v$-reduced} if for any nonempty subset~$U\subseteq V\setminus \{v\}$ the divisor~$D-Q(G)\one_U$ is not effective\footnote{The definition of $v$-reduced divisor can be extended to all divisors by allowing $D(v)$ to be negative for a $v$-reduced divisor~$D$ as is done in~\cite{BakerNorine2007}. However, in this paper we will mostly deal with effective divisors.}. In other words, for every nonempty~$U\subseteq V\setminus \{v\}$ there is a~$u\in U$ with $D(u)<|E(\{u\}, V\setminus U)|$. \begin{lemma}[{\cite[Proposition~3.1]{BakerNorine2007}}]\label{reduction} Let $v\in V$ and let $D$ be an effective divisor on~$G$. Then there is a unique $v$-reduced divisor equivalent to~$D$. \end{lemma} \begin{proof} For any divisor~$D' \sim D$, there is a unique $x_{D'}\in \{x\in \Z^V\mid x(v)=0\}$ such that~$D'=D-Q(G)x_{D'}$ by Lemma~\ref{Laplacian}. Let \begin{equation} S\coloneqq \{x_{D'}\mid D'\text{ is effective and equivalent to~$D$}\}. \end{equation} The set~$S$ is finite since the number of effective divisors equivalent to~$D$ is finite. The set~$S$ is nonempty as it contains the zero vector. Choose~$x_{D'}\in S$ maximizing $\sum_{u\in V} x_{D'}(u)$. Then $D'$ is $v$-reduced because for any nonempty~$U\subseteq V\setminus \{v\}$, the vector~$x_{D'}+\one_U$ is not in~$S$ by the choice of~$x_{D'}$. To show uniqueness, let $D$ and~$D'$ be two different, but equivalent effective divisors. It suffices to show that $D$ and~$D'$ are not both $v$-reduced. By Lemma~\ref{chain} there are sets~$\emptyset\subsetneq U_1\subseteq\cdots\subseteq U_k\subsetneq V$ such that $D-Q(G)\one_{U_1}$ and $D'+Q(G)\one_{U_k}=D'-Q(G)\one_{V\setminus U_k}$ are effective. If $v\not\in U_1$, then $D$ is not $v$-reduced. If $v\in U_1$, then $v\not\in V\setminus U_k\subseteq V\setminus U_1$ and hence $D'$ is not $v$-reduced. \end{proof} \begin{rema} Observe that if $D$ is a $v$-reduced divisor, then $D(v)\geq D'(v)$ for any effective divisor~$D'\sim D$. Indeed, by Lemma~\ref{chain} we obtain $D'$ from~$D$ by firing on a chain of sets $U_1\subseteq\cdots\subseteq U_t$ and, since $D$ is $v$-reduced, we have $v\in U_1$. We conclude that if $D$ is a $v$ reduced divisor of positive rank, we have $D(v)\geq 1$. \end{rema} We say that an effective divisor~$D$ \emph{covers} $v\in V$ if there is an effective divisor~$D'$ equivalent to~$D$ with $v\in \supp(D')$. We call a nonempty subset~$S\subseteq V$ a \emph{strong separator} if for each component~$C$ of $G[V\setminus S]$ we have that $C$ is a tree and $|E(\{s\},V(C))|\leq 1$ for every~$s\in S$. The following lemma is similar to a theorem of Luo~\cite{Luo2011} on rank determining sets in the context of metric graphs. \begin{lemma}\label{Luotype} Let $S$ be a strong separator of~$G$ and let $D$ be an effective divisor covering every~$s\in S$. Then $D$ has positive rank. \end{lemma} \begin{proof} Since any superset of a strong separator is again a strong separator, we may assume that \begin{equation} S=\{s\in V\mid \text{$s$ is covered by $D$}\}. \label{eqn:S-assumption} \end{equation} We have to show that $S=V$. Suppose not. Let $C$ be a component of $G[V\setminus S]$ and let $S'\coloneqq \{s\in S: |E(\{s\},V(C))|=1\}$. Since $G$ is connected, $S'$ is not empty, so we may take $s\in S'$ and assume that $D$ is $s$-reduced. If $S'\subseteq \supp(D)$, then $D+Q(G)\one_{V(C)}$ is effective and has support on at least one vertex in $V(C)\subseteq V\setminus S$, but this contradicts~\eqref{eqn:S-assumption}. Therefore, $S' \not\subseteq \supp(D)$. Choose $t\in S'\setminus \supp(D)$. By~\eqref{eqn:S-assumption}, $t$ is covered by~$D$. However, $t$ is not in the support of~$D$, so in particular $D$ is not $t$-reduced. Let $a$ and $b$ be the unique neighbours of $s$~and~$t$ in~$V(C)$, respectively, and let $P=(s,a,\ldots,b,t)$ be the path from~$s$ to~$t$ with its interior points in~$V(C)$. Since $D$ is $s$-reduced, but not $t$-reduced, there is a set~$U\subseteq V$ with $s\in U$, $t\not\in U$ such that $D'\coloneqq D-Q(G)\one_U$ is effective. The cut~$E(U,V\setminus U)$ must intersect some edge~$e=uv$ of the path~$P$, and we find that $D(u)\geq 1$ and $D'(v)\geq 1$. This contradicts~\eqref{eqn:S-assumption}, since at least one of $u$~and~$v$ is in~$V(C)\subseteq V\setminus S$. \end{proof} \begin{coro} \label{rankdetermining} If $H$ is a subdivision of~$G$ and $D$ is a divisor on~$H$ that covers all~$v\in V(G)$, then $D$ has positive rank. \end{coro} Corollary~\ref{rankdetermining} can be seen as a discrete analogue of~\cite[Theorem~1.6]{Luo2011}\footnote{In the preprint of~\cite{Luo2011} (\cf \href{https://arxiv.org/abs/0906.2807v2}{arXiv:0906.2807v2}), this is Theorem~1.5 (instead of~1.6).}. \subsection{Treewidth} The notion of \emph{treewidth} was first introduced by Halin~\cite{Halin1976} and later rediscovered by Robertson and Seymour~\cite{RobertsonSeymour1990} as part of their graph minor theory. There are several equivalent definitions of treewidth. We will follow Diestel~\cite{DiestelGraphTheory}, and define treewidth in terms of tree-decompositions. Let $G=(V,E)$ be a graph (we allow multiple edges and loops). Let $(X_i)_{i\in I}$ be a family of vertex sets $X_i\subseteq V$ indexed by the nodes of a tree $T=(I,F)$. The pair $(T,(X_i)_{i\in I})$ is a \emph{tree decomposition} of $G$ if it satisfies the following conditions: \begin{enumerate}[label=(\roman*)] \item $\bigcup_{i\in I} X_i = V$; \item for every edge $e=vw\in E$ there is an $i\in I$ with $v,w\in X_i$; \item if $i,j,k\in I$ and node $j$ is on the path in $T$ between nodes $i$ and $k$, then $X_i\cap X_k\subseteq X_j$. \end{enumerate} The \emph{width} of the tree decomposition is $\max_{i\in I} |X_i|-1$. The \emph{treewidth} of a $G$ is the minimum width of a tree decomposition of $G$. In order to use treewidth as a lower bound, we will use a characterisation of treewidth by Seymour and Thomas~\cite{SeymourThomas1993} in terms of ``brambles''.\footnote{The article of Seymour and Thomas~\cite{SeymourThomas1993} used the term \emph{screen} instead of \emph{bramble}, but the latter has since become the standard.} Let $G=(V,E)$ be a graph, and let $2^V$ denote the power set of $V$. A set $\B\subseteq 2^V\setminus\{\emptyset\}$ is called a \emph{bramble} if for any $B,B'\in \B$ the induced subgraph $G[B\cup B']$ is connected. In particular, $G[B]$ is connected for every $B\in \B$. For any $B,B'\in \B$, either $B\cap B'\neq \emptyset$, or $B\cap B'=\emptyset$ and there is an edge in $E(B,B')$. In the latter case, we say that $B$ and $B'$ \emph{touch}. A set $S\subseteq V$ is called a \emph{hitting set} for $\B$ if it has nonempty intersection with every member of $\B$. The \emph{order} of $\B$, denoted $\order{\B}$, is the minimum size of a hitting set for $\B$. That is: \begin{equation} \order{\B}\coloneqq \min \{|S| : S\subseteq V, S\cap B\neq\emptyset \text{ for all $B\in \B$}\}. \end{equation} The following theorem by Seymour and Thomas~\cite{SeymourThomas1993} gives a min-max characterisation of treewidth. \begin{theorem}[{treewidth duality, \cite[Theorem~1.4]{SeymourThomas1993}}] Let $k\geq 0$ be an integer. A graph $G$ has treewidth at least $k$ if and only if it has a bramble of order at least $k + 1$. \end{theorem} \begin{rema} We note that the treewidth of a graph is equal to the treewidth of the underlying simple graph, as can be seen directly from the definition. It is well-known that treewidth is monotone under taking minors (see for example~\cite{DiestelGraphTheory}). That is, removing or contracting edges can only decrease treewidth. In particular, if $H$ is a subdivision of $G$, then $\tw(G)\leq \tw(H)$. \end{rema} We refer the interested reader to Chapter~12 in~\cite{DiestelGraphTheory} for an excellent exposition of treewidth and its role in the graph minor theory. \section{Proof of the main theorem} In this section we prove our main theorem. \begin{theorem}\label{main} Let $G=(V,E)$ be a connected graph. Then $\dgon(G)\geq \tw(G)$. \end{theorem} We start by stating and proving two lemmas. \begin{lemma}\label{oneside} Let $D,D'$ be effective divisors such that $D'=D-Q(G)\one_U$ for some subset $U\subseteq V$. Let $B\subseteq V$ be such that $G[B]$ is connected. Suppose that $B\cap \supp(D)$ is nonempty, but $B\cap \supp(D')$ is empty. Then $B\subseteq U$. \end{lemma} \begin{proof} Clearly, $B$ cannot be a subset of $V\setminus U$, because otherwise $D'(v)\geq D(v)$ for every $v\in B$. Now suppose that $B\cap U$ and $B\setminus U$ are both nonempty. Since $G[B]$ is connected, there is an edge $uv$ with $u\in B\cap U$ and $v\in B\setminus U$. But then $D'(v)=(D-Q(G)\one_U)(v)\geq D(v)+1\geq 1$ since $u\in U$ is a neighbour of $v\in V\setminus U$. This is a contradiction as well, so we see that $B\subseteq U$ must hold. \end{proof} \begin{lemma}\label{brambleseparation} Let $\B$ be a bramble in $G$ and let $U\subseteq V$. Suppose that there exist $B,B'\in \B$ such that $B\subseteq V\setminus U$ and $B'\subseteq U$. Then $|E(U,V\setminus U)|+1\geq \order{\B}$. \end{lemma} \begin{proof} We will construct a hitting set for $\B$ of size at most $|E(U,V\setminus U)|+1$. Let $F\coloneqq E(U,V\setminus U)$ be the cut determined by $U$ and let $H\coloneqq (V,F)$. Let \[ X\coloneqq \{v\in U\mid d_H(v)\geq 1\}\qquad\text{and}\qquad Y\coloneqq \{v\in V\setminus U\mid d_H(v)\geq 1\} \] be the ``shores'' of the cut $F$. Let $B\in \B$ be such that $B\subseteq V\setminus U$. Let $\B'\coloneqq \{B'\in \B\mid B'\subseteq U\}$. By assumption, $\B'$ is nonempty. Choose $B'\in \B'$ for which $B'\cap X$ is inclusion-wise minimal. Observe that $B'\cap X$ is nonempty, since $B'$ must touch $B$. We now define a hitting set~$S$ for~$\B$ as follows. Add an arbitrary element~$s$ from \hbox{$B'\cap X$} to~$S$. For each edge~$xy\in E(X,Y)$ with $x\in X, y\in Y$, we add $x$ to~$S$ if $x\not\in B'$, and otherwise we add $y$ to~$S$. Hence $|S|\leq 1+|F|$. See Figure~\ref{hittingset} for a depiction of the situation. \begin{figure}[htb]\centering \hittingsetTikZ \caption{The hitting set $S$ for the bramble $\B$ is formed by the black vertices.\label{hittingset}} \end{figure} %\medskip To prove that $S$ covers $\B$, consider any $A\in \B$. First observe that $A$ intersects $X\cup Y$. Otherwise, we would have $A\subseteq U\setminus X$ or $A\subseteq (V\setminus U)\setminus Y$ as $G[A]$ is connected. In the first case $G[A\cup B]$ is not connected and in the second case $G[A\cup B']$ is not connected. In both cases, this contradicts the fact that $\B$ is a bramble. We consider the following three cases. \begin{itemize} \item Case $A\cap Y=\emptyset$.\quad In this case $A\subseteq U$. By the choice of $B'$, we have either $B'\cap X\subseteq A\cap X$ and hence $s\in A$, or there exists an $x\in (X\cap A)\setminus B'$, which implies that $x\in S$. In both situations $S$ intersects $A$. \item Case $A\cap X=\emptyset$.\quad In this case $A\subseteq (V\setminus U)$. Since $A$ touches $B'$, there must be an edge $e=xy$ with $x\in B'\cap X$ and $y\in A\cap Y$. By construction of $S$ we have $y\in S$. Hence, $S$ intersects $A$. \item Case $A\cap X\neq \emptyset$ and $A\cap Y\neq \emptyset$.\quad Since $G[A]$ is connected, there is an edge $e=xy$ with $x\in X$, $y\in Y$ and $x,y\in A$. Since $S$ contains at least one endpoint from each edge in $F$, the set $S$ must intersect $A$. \end{itemize} We conclude that $S$ is a hitting set for $\B$ of size at most $|E(U,V\setminus U)|+1$, which proves the lemma. \end{proof} \noindent We now prove the main theorem. \begin{proof}[Proof of Theorem~\ref{main}] Let $\B$ be a bramble in $G$ of maximum order. That is, $\order{\B} = \tw(G)+1$. Let $D'$ be an effective divisor of positive rank and degree $\dgon(G)$. Among the effective divisors equivalent to $D'$, we choose $D$ such that $\supp(D)$ intersects a maximum number of sets in $\B$. If $\supp(D)$ is a hitting set for $\B$, then we are done: \begin{equation} \dgon(G)=\deg(D) \geq |\supp(D)| \geq \order{\B} = \tw(G)+1. \end{equation} We may therefore suppose that $B\in\B$ is not intersected by $\supp(D)$ and let $v\in B$. Since $D$ has positive rank and $D(v)=0$, it follows that $D$ is not $v$-reduced. Hence, by Lemma~\ref{chain}, there exist a chain $\emptyset\subsetneq U_1\subseteq\ldots\subseteq U_k\subseteq V\setminus{\{v\}}$ and a sequence of equivalent effective divisors $D_0\coloneqq D,D_1,\ldots,D_k$ such that $D_k$ is $v$-reduced and for every $i=1,\ldots, k$ we have $D_i=D_{i-1}-Q(G)\one_{U_i}$. Since $D$ has positive rank, $\supp(D_k)$ contains $v$ and hence intersects $B$. Let $i\leq k$ be the smallest index such that there is a $B'\in \B$ that is intersected by $\supp(D_0)$ but not by $\supp(D_i)$. Such an index exists, since otherwise $\supp(D_k)$ intersects more members of $\B$ then $\supp(D_0)$, contradicting our choice of $D=D_0$. From $B'\cap \supp(D_{i-1})\neq \emptyset$ and $B'\cap \supp(D_{i})=\emptyset$ it follows by Lemma~\ref{oneside} that $B'\subseteq U_i$. %\looseness-1 By definition of $i$, the set $\supp(D_{i-1})$ intersects every member of $\B$ that is intersected by $\supp(D)$. By our choice of $D$, the set $\supp(D)$ intersects at least as many members of $\B$ as $\supp(D_{i-1})$ does. Hence it follows that $\supp(D_{i-1})$ does not intersect~$B$. Since $\supp(D_k)$ does intersect $B$, there is an index $j\geq i$ such that $B\cap \supp(D_{j-1})=\emptyset$ and $B\cap \supp(D_{j})\neq\emptyset$. Hence, since $D_{j-1}=D_j-Q(G)\one_{V\setminus U_j}$, we have $B\subseteq V\setminus U_j$ by Lemma~\ref{oneside}. This implies that also $B\subseteq V\setminus U_i$. Since $B\subseteq V\setminus U_i$ and $B'\subseteq U_i$, it follows by Lemma~\ref{brambleseparation} that $|E(U_i,V\setminus U_i)|\geq \order{\B}-1$. Since \begin{equation} \deg (D_{i-1})\geq \sum_{u\in U_i}D_{i-1}(u)\geq |E(U_i,V\setminus U_i)|, \end{equation} it follows that $\dgon(G)=\deg(D) = \deg(D_{i-1}) \geq \order{\B} - 1 = \tw(G)$. \end{proof} \section{Examples} In this section, we describe some examples of (classes of) graphs for which equality holds in $\tw(G)\leq \dgon(G)$. To prove equality it suffices in each case to exhibit a positive rank divisor~$D$ and a bramble~$\B$ such that $\order{\B}-1\geq \deg(D)$. \begin{exam} As a concrete example, consider the Petersen graph~$G$ depicted in Figure~\ref{fig:Petersen}. The bramble $\B\coloneqq \{\{1,6\},\{2,7\},\{3,8\},\{4,9\},\{5,10\}\}$ (depicted on the left) has order~$5$ since the five sets in~$\B$ are disjoint. The divisor~$D$ with $D_v=1$ for $v=3,5,6,7$ and $D_v=0$ for all other vertices~$v$ (depicted on the right) is a positive rank divisor of degree~$4$. That $D$ has positive rank follows since we can fire on the complements of the sets $\{1,2\}$, $\{4,9\}$, and $\{8,10\}$. It follows that \[ 4=\order{\B}-1\leq \tw(G)\leq \dgon(G)\leq 4. \] So the Petersen graph has gonality and treewidth equal to~$4$. \begin{figure}[ht]\centering %\begin{center} \PetersenTikZa\qquad\qquad\qquad\PetersenTikZb %\end{center} \caption{Petersen graph with a bramble of order~$5$ and a positive rank divisor of degree~$4$.\label{fig:Petersen}} \end{figure} \end{exam} \begin{exam} Let $G=(V,E)$ be a \emph{simple} graph with at least one edge. Let $g\coloneqq |E|-|V|+1$ be its circuit rank. If $g=0$, then $G$ is a tree and $\tw(G)=\dgon(G)=1$. If $g\in\{1,2\}$, we have $\tw(G)=\dgon(G)=2$ as is readily verified. \end{exam} \begin{exam}[Complete $k$-partite graph] Let $G=(V,E)$ be a complete $k$-partite graph, $k\geq 2$, with partition $V=V_1\cup\cdots\cup V_k$, where $n_i\coloneqq |V_i|\geq 1$. We may assume that $n_1\leq n_2\leq \cdots\leq n_k$. For $i=1,\ldots, k$ let~$s_i\in V_i$ and consider the bramble~$\B\coloneqq \{\{s_1\},\ldots,\{s_k\}\}\cup\{\{u,v\}\mid uv\in E\}$. A set~$S\subseteq V$ is a hitting set for~$\B$ if and only if $s_1,\ldots,s_k\in S$ and there is at most one index~$i$ such that $V_i\not\subseteq S$. Hence a hitting set of minimal cardinality is given by $S\coloneqq V_1\cup\cdots\cup V_{k-1}\cup\{s_k\}$. Hence $\tw(G)\geq \order{\B}-1=n_1+\cdots+n_{k-1}$. Let $D\coloneqq \one_{V_1\cup\cdots\cup V_{k-1}}$. For every~$v\in V_k$, the divisor $D+Q(G)\one_{\{v\}}$ is effective. Hence, $D$ has rank at least one and therefore $\dgon(G)\leq n_1+\cdots+n_{k-1}$. We conclude that $\tw(G)=\dgon(G)=n_1+\cdots+n_{k-1}$. In particular we have $\dgon(K_n)=n-1$ for the complete graph on $n$ vertices, and $\dgon(K_{m,n})=m$ for the complete bipartite graph with colour classes of sizes $m\leq n$. For the octahedron $K_{2,2,2}$ we find $\dgon(K_{2,2,2})=4$. \end{exam} \begin{exam}[Rectangular grid] Let $m\leq n$ be integers and let $G=(V,E)$ be the $(m+1)\times (n+1)$ rectangular grid. That is, $V\coloneqq [m+1]\times [n+1]$ and two vertices $(a,b)$~and~$(a',b')$ form an edge if $|a-a'|+|b-b'|=1$. Let $A\coloneqq [m+1]\times \{n+1\}$ and $B\coloneqq \{m+1\}\times [n]$. For $i\in [m]$ and $j\in [n]$ consider the ``cross'' \[ C_{ij}\coloneqq \{(a,b)\in [m]\times [n]\mid \text{$a=i$ or $b=j$}\}. \] It is easy to see that $\B\coloneqq \{A,B\}\cup\{C_{ij}\}_{i\in [m], j\in [n]}$ is a bramble. Any hitting set for the $C_{ij}$ contains at least $m$ elements from $[m]\times [n]$ (one from each row). Hence, since $A$, $B$, and $[m]\times [n]$ are disjoint, the order of $\B$ is at least $m+2$. On the other hand, take the divisors~$D_i\coloneqq \one_{[m+1]\times\{i\}}$ for~$i=1,\ldots, n+1$. These divisors are equivalent, since $D_{i+1}=D_i-Q(G)\one_{[m+1]\times [i]}$ for $i=1,\ldots, n$. Hence, since every~$(a,b)\in V$ is in the support of some $D_b$, the rank of $D_1$ is at least one. Therefore we can conclude that $m+1\leq \tw(G)\leq \dgon(G)\leq m+1$, and hence $\dgon(G)=\tw(G)=m+1$. \end{exam} An interesting family for which we do not know the answer is the following. Let $Q_n$ be the $n$-dimensional cube. That is, $Q_n$ is the graph with vertex set $\{0,1\}^n$ and two vertices $x,y$ are connected by an edge if $x$ and $y$ differ in exactly one coordinate. It is clear that $\dgon(Q_n)\leq 2^{n-1}$ and we believe that equality holds. On the other hand, $\tw(Q_n)=\Theta(\frac{2^n}{\sqrt{n}})$; see~\cite{SunilKavitha2006}. \section{Metric graphs} In this section, we show that for any metric graph $\Gamma$ (tropical curve) with underlying connected graph $G$, there is a subdivision $H$ of $G$, such that $\dgon(H)\leq \dgon(\Gamma)$. Hence, the treewidth is also a lower bound for metric graphs: \begin{equation}\tw(G)\leq \tw(H)\leq \dgon(H)\leq \dgon(\Gamma).\end{equation} Let $G=(V,E)$ be a connected graph, and let $l:E\to \R_{>0}$ be a length function on the edges. Associated to the pair $(G,l)$ is the \emph{metric graph} $\Gamma$ which is the compact connected metric space obtained by identifying every edge $e$ with a real interval of length $l(e)$ and glueing edges along common endpoints. The free abelian group on the points of $\Gamma$ is denoted $\Div(\Gamma)$ and the elements of $\Div(\Gamma)$ are called \emph{divisors} on $\Gamma$. For $D=c_1v_1+\cdots+c_kv_k\in \Div(\Gamma)$, with $c_1,\ldots, c_k\in \Z\setminus\{0\}$ and $v_1,\ldots, v_k\in \Gamma$ distinct, the \emph{degree} of $D$ is defined as $\deg(D)\coloneqq c_1+\cdots+c_k$ and the \emph{support} of $D$ is denoted $\supp (D)\coloneqq \{v_1,\ldots, v_k\}$. The divisor is \emph{effective} if $c_1,\ldots, c_k>0$. A \emph{rational function} on $\Gamma$ is a continuous real valued function on $\Gamma$ such that its restriction to any edge is piecewise linear with finitely many pieces and integral slopes. The set of rational functions on $\Gamma$ is denoted $\Rat(\Gamma)$. Let $f\in \Rat(\Gamma)$. For each $v\in \Gamma$, let $c_v$ be the sum of the outgoing slopes of $f$ at $v$. So $c_v\neq 0$ only for breakpoints of $f$ (which may include points in $V$). The associated divisor is denoted $\todiv(f)\coloneqq \sum_{v\in \Gamma} c_vv$ and is called a \emph{principal} divisor. The set of principal divisors is denoted $\Prin(\Gamma)$ and is a subgroup of $\Div(\Gamma)$. Two divisors are \emph{equivalent} if their difference is a principal divisor. Observe that a principal divisor has degree $0$, and hence equivalent divisors have equal degrees. For a point $v\in \Gamma$, we say that an effective divisor $D$ \emph{covers} $v$ if there exists an effective divisor equivalent to $D$ with $v$ in its support. The \emph{gonality} $\dgon(\Gamma)$ is defined as the minimum degree of a divisor that covers every point $v\in \Gamma$. It was proven in~\cite{Luo2011} that if $D$ covers every $v\in V$, then $D$ covers every $v\in \Gamma$. However, we will not use that result here. For any subset $S\subseteq \Gamma$, we denote \begin{align} \Div_S(\Gamma)&\coloneqq \{D\in \Div(\Gamma)\mid \supp(D)\subseteq S\},\\ \Rat_S(\Gamma)&\coloneqq \{f\in \Rat(\Gamma)\mid \todiv(f)\in \Div_S(\Gamma)\},\\ \Prin_S(\Gamma)&\coloneqq \{\todiv(f)\mid f\in \Rat_S(\Gamma)\}. \end{align} Observe that $\Prin_S(\Gamma)=\Div_S(\Gamma)\cap \Prin(\Gamma)$ and that two divisors $D,D'\in \Div_S(\Gamma)$ are equivalent if and only if $D-D'\in \Prin_S(\Gamma)$. The elements of $\Div_V(\Gamma)$ can be identified with the corresponding elements in $\Z^V$ and thus viewed as the divisors on the graph $G$. Up to adding a constant function, the elements of $\Rat_V(\Gamma)$ are determined by their integral slopes of the edges of $G$. To this end, we fix an arbitrary orientation on $G$, and define the map $\phi:\Rat_V(\Gamma)\to \Z^E$ by setting $\phi(f)(e)$ to be the slope of $f$ on edge $e$ (in the forward direction). It is easy to see that $g\in \Z^E$ is in the image of $\phi$ if and only if \begin{equation}\label{cycles} \sum_{e\in E} g(e)l(e)\chi_C(e)=0\quad \text{for every cycle $C$ in $G$}. \end{equation} Observe that for $f\in\Rat_V(\Gamma)$ we have: $\todiv(f)=-M \phi(f)$, where $M$ is the signed vertex-edge incidence matrix of $G$. In the case $l=\one$, if follows from~\eqref{cycles} and Lemma~\ref{clattice} that $\phi\left[\Rat_V(\Gamma)\right]=M^\transp\cdot\Z^V$. Hence \begin{equation} \begin{aligned}[t] \Prin(G)&=Q(G)\cdot\Z^V=MM^{\transp}\cdot\Z^V=M\cdot\phi\left[\Rat_V(\Gamma)\right]\\ &=\todiv\left[\Rat_V(\Gamma)\right]=\Prin_V(\Gamma). \end{aligned} \end{equation} Thus, two divisors in $\Div_V(\Gamma)$ are equivalent if and only if they are equivalent as divisors on $G$. \begin{theorem}\label{thm:metricToCombinatorial} Let $\Gamma$ be the metric graph associated to $(G,l)$. Then there is a subdivision $H$ of $G$ such that $\dgon(\Gamma)\geq \dgon(H)$. \end{theorem} \begin{proof} Let $D$ be a minimum degree effective divisor covering $\Gamma$. In particular, $D$ covers every $v\in V$. Hence, for every $v\in V$, there is an effective divisor $D_v$ equivalent to $D$ with $v$ in its support. Let $V'\coloneqq V\cup \supp(D)\cup\bigcup_{v\in V}\supp(D_v)$. Let $\Gamma'$ be obtained by subdividing $\Gamma$ at the points in $V'\setminus V$. Denote by $G'$ and $l'$ the corresponding underlying graph and length function so that $\Gamma'$ is the metric graph associated with $(G',l')$. The divisor $D$ and the divisors $D_v$ can now be seen as equivalent elements of $\Div_{V'}(\Gamma')$. For all $v\in V$, let $f_v\in \Rat_{V'}(\Gamma')$ be such that $D-\todiv(f_v)=D_v$. We equip $G'$ with an arbitrary orientation. It follows that $y=l'$ is a solution to the system \begin{equation}\label{cycle} \sum_{e\in G'}\phi(f_v)(e)y(e)\chi_C(e)=0\quad \text{for every cycle $C$ in $G'$ and every $v\in V$}. \end{equation} Since~\eqref{cycle} is a finite rational linear system in $y$, and since $l'>0$ is a solution, the system also has a solution $l''\in \Z_{>0}^{E'}$. It follows that the $D_v$ are equivalent divisors on the metric graph associated with $(G', l'')$. Subdividing every edge $e$ of $G'$ into $l''$ parts to obtain a graph $H$, we can view the $D_v$ as equivalent divisors in $\Div_{V'}(\Gamma'')$, where $\Gamma''$ is the metric graph associated to $(H,\one)$ in which all edges have length one. Finally, this implies that the $D_v$ are also equivalent as divisors of $H$. It follows that for any $v\in V$, the divisor $D_v\in \Div(H)$ covers $V\subseteq V(H)$, and hence by Corollary~\ref{rankdetermining} has positive rank. \end{proof} Since $\tw(H)\geq \tw(G)$ for any subdivision $H$ of $G$, Theorem~\ref{thm:metricToCombinatorial} is now immediate. \begin{coro}\label{lem:LBmetric} Let $\Gamma$ be a metric graph with underlying connected graph $G$. Then $\dgon(\Gamma)\geq \tw(G)$. \end{coro} \begin{rema} Following~\cite{gathmannkerber}, a \emph{tropical curve} is a metric graph with ``unbounded ends''. That is, we allow edges incident to a leaf vertex to have infinite length. In that case, the edge is identified with the closed interval $\mathbb{R}_{\geq 0}\cup\{\infty\}$ where the end at $\infty$, called an \emph{unbounded end} of $\Gamma$, corresponds to the leaf vertex. Rational functions must then be allowed to take the values $\pm \infty$ at the unbounded ends. For any edge $uv$ with unbounded end $v$ and any $w$ on the edge $uv$, there is a rational function $f$ with $\todiv(f)=-u+w$. Hence, we may remove all unbounded ends without decreasing the gonality. It follows that Corollary \ref{lem:LBmetric} holds for tropical curves as well. \end{rema} \section{Other notions of gonality} Other notions of gonality of a graph $G$ have been proposed by Caporaso~\cite{Caporaso2012} and by Cornelissen, Kato, and Kool in~\cite{CornelissenKatoKool2012}. These notions are based on harmonic morphisms from $G$ to a tree. Here we will show that treewidth is also a lower bound for the gonality in these cases. Again, we assume that our graphs are connected, finite, and loopless (but possibly with multiple edges). We follow terminology from~\cite{BakerNorine2009}. A \emph{morphism from $G=(V,E)$ to $G'=(V',E')$}, is a map $\phi:V\cup E\to V'\cup E'$ such that \begin{enumerate}[label=(\roman*),series=morphism] \item $\phi(V)\subseteq V'$, \item if $e\in E(u,v)$, then either $\phi(e)=\phi(u)=\phi(v)$, or $\phi(e)\in E'(\phi(u),\phi(v))$. \end{enumerate} If $\phi(E)\subseteq E'$, then $\phi$ is called a \emph{homomorphism}. We call a morphism $\phi$ \emph{harmonic} if \begin{enumerate}[resume*=morphism] \item for every $v\in V$ there exists a nonnegative integer $m_\phi(v)$ such that \begin{equation}\label{harm} m_\phi(v)=|\phi^{-1}(e')\cap E(v)|\quad\text{for every $e'\in E'(\phi(v))$,} \end{equation} \end{enumerate} \noindent and \emph{non-degenerate} if in addition \begin{enumerate}[resume*=morphism] \item $m_\phi(v)\geq 1\quad$ for every $v\in V$. \end{enumerate} \noindent If $\phi$ is harmonic, then there is a number $\deg(\phi)$ such that for every edge $e'\in E'$ and every $v'\in V'$ \[ \deg(\phi)=|\phi^{-1}(e')|=\sum_{v\in \phi^{-1}(v')}m_\phi(v). \] \begin{lemma} Let $G=(V,E)$ and $G'=(V',E')$ be graphs and let $\phi:G\to G'$ be a non-degenerate harmonic morphism. Then $\dgon(G)\leq \dgon(G')\deg(\phi)$. In particular, $\dgon(G)\leq \deg(\phi)$ when $G'$ is a tree. \end{lemma} \begin{proof} For any divisor $D\in \Div(G')$, define the divisor $\phi^*(D)\in \Div(G)$ by $\phi^*(D)(v)\coloneqq m_\phi(v)D(\phi(v))$. Observe that $\deg(\phi^*(D))=\deg(D)\deg(\phi)$ (\cf \cite[Lemma~2.8]{BakerNorine2009}\footnote{In the preprint of~\cite{BakerNorine2009} (\cf \href{https://arxiv.org/abs/0707.1309v2}{arXiv:0707.1309v2}), this is Lemma~2.13 (instead of~2.8).}), and that $\supp(\phi^*(D)) = \phi^{-1}(\supp(D))$ by non-degeneracy of $\phi$. If $D$ is effective, then so is $\phi^*(D)$. It is easy to see that if $D,D'\in \Div(G')$ are equivalent, then $\phi^*(D)$ and $\phi^*(D')$ are equivalent as well. Indeed, for any $y\in \Z^{V'}$ we have $\phi^*(Q(G')y)=Q(G)x$, where $x(u)\coloneqq y(\phi(u))$. Hence, if $D\in\Div(G')$ is an effective divisor of positive rank in $G'$, then $\phi^*(D)$ is an effective divisor of positive rank in $G$ with $\deg(\phi^*(D))=\deg(D)\deg(\phi)$. \end{proof} The notion of harmonic morphism can be extended to \emph{indexed harmonic morphism} by associating to every edge $e\in \phi^{-1}(E')$ a positive integer $r_e$ and counting in~\eqref{harm} every edge $e\in \phi^{-1}(e')$ with multiplicity $r_e$. Hence, an indexed harmonic morphism $G\to G'$ corresponds to a harmonic morphism $H\to G'$, where $H$ is obtained from $G$ by replacing every edge $e$ by $r_e$ parallel edges which are mapped to the same edge as the original edge $e$. In~\cite{Caporaso2012}, Caporaso defined the gonality of a graph $G$ as the minimum degree of a non-degenerate indexed harmonic morphism (with some additional restriction) from $G$ to a tree. Hence it follows that this measure of gonality is lower bounded by $\dgon(H)$ for some $H$ obtained from $G$ by adding parallel edges, and hence by $\tw(H)=\tw(G)$. In~\cite{CornelissenKatoKool2012}, Cornelissen, Kato and Kool define the \emph{stable gonality} $\sgon(G)$ of $G$ to be the minimum degree of an indexed harmonic homomorphism from a \emph{refinement} of $G$ to a tree $T$. Note that a harmonic homomorphism is automatically non-degenerate. A refinement of $G$ is a graph obtained from $G$ by subdividing edges and adding leaves (vertices of degree 1). Therefore $\sgon(G)$ is lower bounded by $\dgon(H)$ for some graph $H$ obtained from $G$ by subdividing edges, adding leaves and adding parallel edges. Hence, $\sgon(G)\geq \dgon(H)\geq \tw(H)\geq \tw(G)$. For a further comparison of the different notions of gonality, we refer the reader to~\cite{CornelissenKatoKool2012}. \longthanks{We would like to thank Maarten Derickx. He was the first to prove that the gonality of the $n\times m$ grid equals $\min(m,n)$ (unpublished). His method inspired us to conjecture and prove that $\tw(G)\leq \dgon(G)$. The second author would also like to thank Jan Draisma for some stimulating discussions on graph gonality. Finally, we thank Remy van Dobben de Bruyn for many comments on earlier versions of this manuscript.} \bibliographystyle{amsplain-ac} \bibliography{ALCO_Gijswijt_357} \end{document}