Upper bounds of orders of automorphism groups of leafless metric graphs

Abstract

We prove a tropical analogue of the theorem of Hurwitz: A leafless metric graph of genus $g\ge 2$ has at most 12 automorphisms when g = 2 and $2^{g}g!$ automorphisms when $g\ge 3$. These inequalities are optimal; for each genus, we give all metric graphs which have the maximum numbers of automorphisms. The proof is written in terms of graph theory.

Keywords:

• Tropical curves
• automorphisms of graphs
• Betti numbers of graphs
• tropical analogue of the theorem of Hurwitz

2020 Mathematics Subject Classification:

• Primary: 14T20
• Secondary: 05C99

1 Introduction

In classical algebraic geometry, the theorem of Hurwitz says that an algebraic curve of genus $g\ge 2$ has at most $84(g-1)$ automorphisms (cf. [3, Ex. 2.5. in Chapter IV]). In this paper, we will prove a tropical analogue of this theorem.

Tropical geometry is, roughly speaking, an algebraic geometry over the tropical semifield $\mathit{T}:=(\mathit{R}\cup \{-\infty \},\max ,+)$ (cf. [5] for an introduction to tropical geometry). The process of passing from classical arithmetic (resp. classical algebro-geometric objects) to tropical arithmetic (resp. tropical objects) is referred to as tropicalization.

Tropicalizations of algebraic curves have abstract tropical curve structures. An abstract tropical curve is an extension of a metric graph. A metric graph is defined as the metric space associated with a pair of an unweighted, undirected, finite, connected nonempty multigraph G which may have loops and a length function $l:E_G\to {\mathit{R}}_{>0}$, where E_G denotes the set of edges of G, by identifying each edge e of G with the closed interval $[0,l(e)]$. For an abstract tropical curve $\Gamma$, we allow l to take the value $\infty$ only on edges incident to leaves. Each point $\infty \in [0,\infty ]$ must be identified with a leaf, where $[0,\infty ]$ is the one-point compactification of $[0,\infty )$. If l takes the value $\infty$, then $\Gamma$ is no longer a metric space, but a topological space (cf. [4] for more details).

An abstract tropical curve $\Gamma$ has a genus in the usual topological sense. It coincides with $\#E_G-\#V_G+1$ for any pair (G, l) defining $\Gamma$, where V_G denotes the set of vertices of G. Nonnegative integer $\#E_G-\#V_G+k$ for a graph G with k connected components is sometimes called the (first) Betti number of G (cf. [2]).

In the category of abstract tropical curves, morphisms between abstract tropical curves are (finite) harmonic morphisms. An automorphism of a metric graph $\Gamma$, i.e., a finite harmonic morphism $\Gamma \to \Gamma$ of degree one is an isometry $\Gamma \to \Gamma$, and vice versa. For a metric graph $\Gamma$, we write its automorphism group as $\text{Aut}(\Gamma )$, which coincides with the isometry group of $\Gamma$.

The following is our main theorem:

Theorem 1.

Let $\Gamma$ be a leafless metric graph of genus $g\ge 2$. Then the inequality $$\#\text{Aut}(\Gamma )\le \{\begin{array}{cc}{2}^{g}g!\hfill & \text{if }g\ge 3,\hfill \\ 12\hfill & \text{if }g=2\hfill \end{array}$$ holds. Furthermore, the inequality becomes an equality if and only if $\Gamma$ is one of the following:

• $\Gamma$ is defined by the pair of $G_{\text{banana},g}$ and some l whose image is one point with g = 2, 3.

• $\Gamma$ is defined by the pair of $G_{\text{bouquet},g}$ and some l whose image is one point with $g\ge 3$.

• $\Gamma$ is defined by the pair of $G_{\text{lollipop},g}$ and some l such that all g loops have the same length and all g bridges have the same length with $g\ge 3$.

Here, an abstract tropical curve is leafless if it has no one-valent points (it is said to be minimal in [1]). The valency of a point x of an abstract tropical curve is the minimum number of connected components of $U\setminus \left\{x\right\}$ with all neighborhoods U of x. For $g\ge 1,G_{\text{banana},g}$ denotes the multigraph that has only two vertices and g + 1 multiple edges between them. For $g\ge 1,G_{\text{bouquet},g}$ denotes the graph that has only one vertex and g loops incident to it. For $g\ge 2,G_{\text{lollipop},g}$ denotes the graph obtained from $G_{\text{bouquet},g}$ by replacing the unique vertex with the star S_g with g leaves.

We note that there are no upper bounds of $\#\text{Aut}(\Gamma )$ without the leafless condition in Theorem 1. Let $\Gamma$ be a metric graph of genus g, and let $v\in \Gamma$ be a point. Let ${\Gamma }^{\prime }$ be the metric graph obtained from $\Gamma$ by attaching 0’s of n copies of the intervals $[0,1]$ to the point v. Then ${\Gamma }^{\prime }$ has genus g, and we have $\#\text{Aut}(\Gamma \prime )\ge n!$ since $\text{Aut}({\Gamma }^{\prime })$ contains the symmetric group of degree n as a subgroup.

In tropical geometry, it is natural to deal only with leafless ones. There is an operation called tropical modification which defines an equivalence relation on all abstract tropical curves. Two abstract tropical curves are equivalent to each other if and only if one of them is obtained from the other by a finite number of retractions that contract a leaf edge to its one point (cf. [1]). Hence for an equivalence class, all representatives have the same genus and there exists a unique leafless representative. For this reason, in tropical geometry, one studies leafless metric graphs for some essential information of their equivalence classes (cf. [6] for higher dimension cases).

Theorem 1 follows the following combinatorial proposition:

Proposition 2.

Let G be a connected leafless graph of Betti number $g\ge 2$. Then the inequality $$\#\text{Aut}(G)\le \{\begin{array}{cc}{2}^{g}g!\hfill & \text{if }g\ge 3,\hfill \\ 12\hfill & \text{if }g=2\hfill \end{array}$$ holds. Furthermore, the inequality becomes an equality if and only if G is one of the following:

1. G is a graph obtained from $G_{\text{banana},g}$ by subdividing all g + 1 edges into the same number ($\ge 1$) of edges with g = 2, 3.

2. G is a graph obtained from $G_{\text{bouquet},g}$ by subdividing all g loops into the same number ($\ge 2$) of edges with $g\ge 3$.

3. G is a graph obtained from $G_{\text{lollipop},g}$ by subdividing all g loops into the same number ($\ge 2$) of edges and all g bridges into the same number ($\ge 1$) of edges with $g\ge 3$.

The rest of this paper is organized as follows. In Section 2, we prepare definitions in graph theory and three lemmas which we need later. Section 3 gives the proofs of the two assertions above.

2 Preliminaries

In this paper, a graph $G=(V_G,E_G,{\epsilon }_G)$ means an undirected finite graph allowing multiple edges and loops. Here, V_G is the finite set of vertices, and E_G is the finite set of edges, and ${\epsilon }_G:E_G\to 2^{V_G}$ is the map that associates an edge $e\in E_G$ with its vertices, where $2^{V_G}$ is the power set of V_G . We note that $\#({\epsilon }_G(e))\in \{1,2\}$ holds for any $e\in E_G$. An edge e is called a loop when $\#({\epsilon }_G(e))=1$. A cut vertex (resp. bridge) of a graph G is a vertex (resp. an edge) whose deletion increases the number of connected components of G. The degree of a vertex is the number of edges incident to it, where a loop is counted twice. A vertex of degree one is called a leaf.

An automorphism $f=(f_V,f_E)$ of a graph G is a pair of bijective maps $f_V:V_G\to V_G$ and $f_E:E_G\to E_G$ satisfying $f_V°{\epsilon }_G={\epsilon }_G°f_E$. $\text{Aut}(G)$ denotes the set of all automorphisms of G. For a subset $S\subset V_G\bigsqcup E_G$, $\text{Aut}{(G)}_S$ denotes the set of all $f\in \text{Aut}(G)$ satisfying $f_V(v)=v$ and $f_E(e)=e$ for any $v\in S\cap V_G$ and $e\in S\cap E_G$. When S consists of only one element x, we sometimes write $\text{Aut}{(G)}_x$ instead of $\text{Aut}{(G)}_{\left\{x\right\}}$. We note that according to this definition, $\#\text{Aut}(G_{\text{bouquet},1})=1$.

Lemma 3.

Let G be a connected leafless graph. Let x be a vertex and let $e_1,\dots ,e_d$ be all the edges incident to x. Let $G^{\prime }$ be the subgraph of G obtained by removing $x,e_1,\dots ,e_d$ from G. Let $G^{″}$ be the maximum subgraph of $G^{\prime }$ in which all vertices have a degree at least two. We set $$S=\left(E_G\setminus E_{G^{″}}\right)\bigsqcup \underset{e\in E_G\setminus E_{G^{″}}}{\cup }{\epsilon }_G(e).$$

Then the following hold.

1. $\text{Aut}{(G)}_{\{x,e_1,\dots ,e_d\}}=\text{Aut}{(G)}_S$.

2. Suppose that $G^{″}\cancel{=}\varnothing$. Then there exists an injective map $\text{Aut}{(G)}_{\{x,e_1,\dots ,e_d\}}\to \text{Aut}{(G^{″})}_y$ for some vertex $y\in V_{G^{″}}$.

Proof.

If G is trivial, then the assertions are clear. Assume that G is not trivial. $G^{″}$ is obtained from $G^{\prime }$ by repeating the following two operations:

1. Removing a vertex v of degree zero.

2. Removing a leaf v and the edge e incident to v.

Let $$G^{\prime }=G_0\supset G_1\supset \cdots \supset G_c=G^{″}$$ be its process. Then, corresponding to the two operations above, the following hold:

1. $E_{G_{i+1}}=E_{G_i}$ and $V_{G_i}\setminus V_{G_{i+1}}=\left\{v\right\}$.

2. $E_{G_i}\setminus E_{G_{i+1}}=\left\{e\right\}$ and $V_{G_i}\setminus V_{G_{i+1}}=\left\{v\right\}$.

We set $$S_i=\left(E_G\setminus E_{G_i}\right)\bigsqcup \underset{e\in E_G\setminus E_{G_i}}{\cup }{\epsilon }_G(e).$$

Since G is connected and nontrivial, $d\ge 1$ holds. Hence $S_0\supset \{x,e_1,\dots ,e_d\}$. By the definition of S₀, we have $\text{Aut}{(G)}_{\{x,e_1,\dots ,e_d\}}=\text{Aut}{(G)}_{S_0}$. Thus, to prove (1), it is sufficient to show that $\text{Aut}{(G)}_{S_i}=\text{Aut}{(G)}_{S_{i+1}}$ for each $0\le i\le c-1$.

The assertion is clear for case (a). Suppose (b). Let u be the end point of e that is not v. Since all vertices of G have a degree at least two, it follows that $v\in S_i$. Furthermore, any edge of G incident to v other than e is contained in S_i . Therefore any $f\in \text{Aut}{(G)}_{S_i}$ fixes e and hence u too. Thus we have $\text{Aut}{(G)}_{S_i}=\text{Aut}{(G)}_{S_{i+1}}$, which completes the proof of (1).

By construction, it follows that $S\cap V_{G^{″}}\cancel{=}\varnothing$ when $G^{″}\cancel{=}\varnothing$. Pick any $y\in S\cap V_{G^{″}}$. Let $f=(f_V,f_E)\in \text{Aut}{(G)}_S$. Since f_V and f_E fix the elements of S, we have $f_V(V_{G″})=V_{G″}$ and $f_E(E_{G^{″}})=E_{G^{″}}$. Therefore, $f^{\prime }=(f_V^{\prime },f_E^{\prime })\in \text{Aut}(G^{″})$ is defined by the restrictions $f_V^{\prime }=f_V{|}_{V_{G^{″}}}$ and $f_E^{\prime }=f_E{|}_{E_{G^{″}}}$. Since $y\in S$, we have $f\prime \in \text{Aut}{(G^{″})}_y$. Therefore, the map $\text{Aut}{(G)}_S\to \text{Aut}{(G^{″})}_y;f\mapsto f^{\prime }$ is induced. This map is injective because we have $V_G\subset V_{G^{″}}\cup S$ and $E_G\subset E_{G^{″}}\cup S$. □

Let G be a graph and $S\subset E_G$. Then the contraction G/S is a graph defined as follows: $$V_{G/S}=V_G/\sim ,\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{E}_{G/S}=E_G\setminus S,\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}{\epsilon }_{G/S}:E_{G/S}\to 2^{V_{G/S}},$$ where ∼ is the minimum relation satisfying $x\sim y$ for any $x,y\in V_G$ with $\{x,y\}\in {\epsilon }_G(S)$, and ${\epsilon }_{G/S}$ is the composition $E_{G/S}\to E_G\stackrel{{\epsilon }_G}{\to }{2}^{V_G}\to 2^{V_{G/S}}$.

Lemma 4.

Let G be a graph and $S\subset E_G$. Let G/S be its contraction. Then the following hold.

1. If S is $\text{Aut}(G)$-invariant, there exists a group homomorphism $\text{Aut}(G)\to \text{Aut}(G/S)$ which commutes with the projection $V_G\to V_{G/S}$ and the inclusion $E_{G/S}\to E_G$.

2. Let S be the set of all bridges of G. Then, the Betti number of G/S is equal to that of G.

3. In addition to (2), we assume that G is leafless. Then the group homomorphism $\text{Aut}(G)\to \text{Aut}(G/S)$ is injective.

Proof.

We shall prove (1). Let $f=(f_V,f_E)\in \text{Aut}(G)$. Let ∼ be the relation on V_G appearing in the definition of the contraction G/S above. Since S is $\text{Aut}(G)$-invariant, we have $f_E(E_G\setminus S)=E_G\setminus S$ and $f_V(x)\sim f_V(y)$ for any $x,y\in V_G$ with $x\sim y$. Therefore, f_V induces the map $f_V^{\prime }:V_{G/S}=V_G/\sim \to V_{G/S}=V_G/\sim$ and $f_E^{\prime }$ is defined by taking the restriction $f_E^{\prime }=f_E{|}_{E_{G/S}}$ to $E_{G/S}=E_G\setminus S$. Since f satisfies $f_E°{\epsilon }_G={\epsilon }_G°f_V$, we have $f_E^{\prime }°{\epsilon }_{G/S}={\epsilon }_{G/S}°f_V^{\prime }$. Hence, we have $f^{\prime }=(f_V^{\prime },f_E^{\prime })\in \text{Aut}(G/S)$. Therefore, we obtain a group homomorphism $\text{Aut}(G)\to \text{Aut}(G/S);f\mapsto f^{\prime }$, which proves (1).

Since S forms the union of trees, we have $\#V_G-\#V_{G/S}=\#E_G-\#E_{G/S}$, which proves (2).

We shall prove (3). Let $f\in \text{Aut}(G)$ be an element whose image in $\text{Aut}(G/S)$ is the identity map. Let H be the subgraph of G such that E_H = S and $V_H=\underset{e\in S}{\cup }{\epsilon }_G(e)$. By assumption, $f\in \text{Aut}{(G)}_F$ holds for $F=(V_G\setminus V_H)\bigsqcup (E_G\setminus E_H)$. Let v be a leaf of H and let e be the edge of H incident to v. First, we shall see that f fixes v. Since v has a degree at least two in G, there exists an edge $e_1\in E_G\setminus E_H$ such that $e_1\cancel{=}e$ and $v\in {\epsilon }_G(e_1)$. If e₁ is a loop, then f fixes v because f fixes e₁. Suppose that e₁ is not a loop. Let $v^{\prime }$ be the end point of e₁ that is not v. Since f fixes e₁, it follows that $f_V(v)=v$ or $f_V(v)=v^{\prime }$. Since S does not contain a circuit, it follows that $v\cancel{\sim }{v}^{\prime }$. On the other hand, since the image of f in $\text{Aut}(G/S)$ is the identity map, we have $f_V(v)\sim v$. Therefore f fixes v. Since f fixes all edges incident to v except e, it also fixes e. Let $v^{″}$ be the end point of e that is not v. Then f also fixes $v^{″}$. Let $H\prime$ be the subgraph of H obtained by removing e and v. Then we have shown that $f\in \text{Aut}{(G)}_{F^{\prime }}$ for $F^{\prime }=(V_G\setminus V_{H^{\prime }})\bigsqcup (E_G\setminus E_{H^{\prime }})$. Since H is a finite union of trees, we can see $f\in \text{Aut}{(G)}_{V_G\bigsqcup E_G}=\left\{{\text{id}}_G\right\}$ by induction, which completes the proof. □

Lemma 5.

1. Let l, m and n be positive integers with $m,n\ge l$. Then we have $$m!n!\le l!(m+n-l)!.$$

2. Let $n_1,\dots ,n_c$ be positive integers. Then we have $$(n_1!)(n_2!)\cdots (n_c!)\le \left(-c+1+\sum _{i=1}^c{n}_i\right)!.$$

The inequality becomes an equality if and only if all but one of $n_1,\dots ,n_c$ are equal to one.

Proof.

(1) is straightforward. By induction on c, (2) is reduced to (1) for l = 1. □

3 Main results

In this section, we will prove the two assertions in Section 1.

The following proposition is valid also for g = 1 in contrast to Proposition 2.

Proposition 6.

Let G be a connected leafless graph of Betti number g and x a vertex of G. Then the inequality $$\#\text{Aut}{(G)}_x\le 2^{g}g!$$ holds.

Proof.

If g = 0, then G is trivial, and the assertion is clear. Therefore we may assume that $g\ge 1$. Furthermore, by Lemma 4, we may assume that G has no bridges.

Let $$G\setminus \left\{x\right\}=U_1\bigsqcup \cdots \bigsqcup U_k$$ be the decomposition to the connected components. Let $G_i=U_i\cup \left\{x\right\}$ be the subgraph of G. Let g_i be the Betti number of G_i . Then $g={\sum }_{i=1}^k{g}_i$ and $g_i\ge 1$ hold. Furthermore, since G has no bridges, each G_i is leafless.

First, we treat the case when k = 1.

Claim 7. When k = 1, the inequality $$\#\text{Aut}{(G)}_x\le 2^{g-d+1}d!(g-d+1)!$$ holds, where d is the number of edges incident to x. In particular, Proposition 6 holds when k = 1.

Proof.

Let $e_1,\dots ,e_d$ be all the edges incident to x. Let $S_d=S\{e_1,\dots ,e_d\}$ denote the permutation group of $\{e_1,\dots ,e_d\}$. Then a group homomorphism s is defined by $$s:\text{Aut}{(G)}_x\to S_d;\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}f\mapsto \left(\begin{array}{cccc}{e}_1& e_2& \cdots & e_d\\ f(e_1)& f(e_2)& \cdots & f(e_d)\end{array}\right).$$

Thus $$\#\text{Aut}{(G)}_x\le \#S_d·\#\text{Ker}(s)=d!·\#\text{Aut}{(G)}_{\{x,e_1,\dots ,e_d\}}$$ hold. We define the subgraph $G^{\prime }$ of G by removing $x,e_1,\dots ,e_d$ from G. Let $G^{″}$ be the maximum subgraph of $G^{\prime }$ in which all vertices have a degree at least two. We note that $G^{\prime }$ and $G^{″}$ are connected since k = 1. Furthermore, $G^{\prime }\cancel{=}\varnothing$ holds unless $G=G_{\text{bouquet},1}$. If $G^{\prime }\cancel{=}\varnothing$, then the Betti number of $G^{\prime }$ is equal to $g-d+1$. In particular, we have $g-d+1\ge 0$.

Suppose $d=g+1$. Then $G^{\prime }$ is a tree, and it follows that $G^{″}=\varnothing$. Then by Lemma 3, $$\#\text{Aut}{(G)}_{\{x,e_1,\dots ,e_d\}}=\#\text{Aut}{(G)}_{V_G\bigsqcup E_G}=1,$$ and hence $$\#\text{Aut}{(G)}_x\le d!·\#\text{Aut}{(G)}_{\{x,e_1,\dots ,e_d\}}=(g+1)!\le 2^{g}g!.$$

Suppose that $g-d+1\ge 1$. If $G=G_{\text{bouquet},1}$, then we have $\#\text{Aut}{(G)}_x=1<2=2^{g-d+1}d!(g-d+1)!$. In what follows, we suppose $G^{″}\cancel{=}\varnothing$. Then we have $d\ge 2$ and the Betti number of $G^{″}$ is equal to $g\prime :=g-d+1$. Then by Lemma 3(2), there exists a vertex y of $G^{″}$ such that $$\#\text{Aut}{(G)}_{\{x,e_1,\dots ,e_d\}}\to \#\text{Aut}{(G^{″})}_y;\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}f\mapsto f{|}_{G^{″}}$$ is injective. Thus, we have $$\#\text{Aut}{(G)}_{\{x,e_1,\dots ,e_d\}}\le \#\text{Aut}{(G^{″})}_y.$$

By induction on the Betti number, we may assume that $$\#\text{Aut}{(G^{″})}_y\le 2^{g^{\prime }}{g}^{\prime }!=2^{g-d+1}(g-d+1)!.$$

Therefore, we have $$\#\text{Aut}{(G)}_x\le 2^{g-d+1}d!(g-d+1)!<2^{g}g!.$$

Here, the second inequality follows from Lemma 5 and $d\ge 2$. □

Suppose $k\ge 2$. Then by $f\in \text{Aut}{(G)}_x$, each G_i is mapped to some G_j . It induces the group homomorphism $$\begin{array}{c}t:\text{Aut}{(G)}_x\to S_k=S\{G_1,\dots ,G_k\};\\ s:\text{Aut}{(G)}_x\to S_d;\mathrm{\hspace{1em}}\mathrm{\hspace{1em}}f\mapsto \left(\begin{array}{cccc}{e}_1& e_2& \cdots & e_d\\ f(e_1)& f(e_2)& \cdots & f(e_d)\end{array}\right).\end{array}$$

Since the kernel $\text{Ker}(t)$ consists of all $f\in \text{Aut}{(G)}_x$ such that $f(G_i)=G_i$ for each i, $$\#\text{Aut}{(G)}_x\le \#S_k·\#\text{Ker}(t)\le k!·\#\text{Aut}{(G_1)}_x\cdots \#\text{Aut}{(G_k)}_x$$

hold. Then, by induction on the Betti number, we have $$\begin{array}{c}\#\text{Aut}{(G)}_x\le k!(2^{g_1}{g}_1!)\cdots (2^{g_k}{g}_k!)\\ =2^g(k!)(g_1!)\cdots (g_k!)\\ \le 2^g\left(-k-1+1+k+\sum _{i=1}^k{g}_i\right)!\\ =2^{g}g!.\end{array}$$

The last inequality follows from Lemma 5. We complete the proof of Proposition 6. □

Remark 8.

In Proposition 6, the equality $\#\text{Aut}{(G)}_x=2^{g}g!$ holds if and only if the pair of G and x is one of the following:

1. G is trivial and x is the unique vertex.

2. G is a subdivision of $G_{\text{banana},1}$ and x is any vertex.

3. G is one of the graphs in (B) of Proposition 2 with $g\ge 2$ and x is the unique cut vertex.

4. G is one of the graphs in (C) of Proposition 2 with $g\ge 2$ and x is the unique cut vertex of S_g .

First, it is clear that G and x in the above list satisfy the equality $\#\text{Aut}{(G)}_x=2^{g}g!$. In what follows, we shall see the inverse implication.

Suppose that G and x satisfy the equality. If g = 0, then G must be (1). Suppose that $g\ge 1$ and G is bridgeless. When k = 1, we have g = 1 by the second inequality in (7.1) in the proof of Claim 7, and the pair (G, x) is confined to (2). When $k\ge 2$, we note that the inequality (6.2) becomes equality only if $g_1=\cdots =g_k=1$. In this case, G must be a subdivision of $G_{\text{bouquet},g}$. For such G, it is clear that only the pairs (G, x) as in (3) satisfy the equality. Finally, suppose that $g\ge 1$ and G has a bridge. Let S be the set of all bridges, and let G/S be the contraction. Then, from what we have already seen, G/S must be one of the graphs in (3). Therefore, the pair (G, x) turns out to be one of the pairs in (4).

Now we can prove Proposition 2.

Proof of Proposition 2.

First, it is clear that G in the list (A), (B), and (C) satisfies the equality (⋆) $$\#\text{Aut}(G)=\{\begin{array}{cc}{2}^{g}g!\hfill & \text{if }g\ge 3,\hfill \\ 12\hfill & \text{if }g=2.\hfill \end{array}$$(⋆)

Suppose that G has a bridge. Let S be the set of all bridges, and let G/S be the contraction. Then by Lemma 4, we have $\#\text{Aut}(G)\le \#\text{Aut}(G/S)$. Furthermore, if G satisfies the equality ($\star$) and if G/S is one of the graphs in (A) and (B), then it is easy to see that G is one of the graphs in (C).

Suppose that G has a loop. Let $G\prime$ be the subdivision of G obtained by adding one vertex to each loop of G. Then $G\prime$ is a loopless graph and we have $\#\text{Aut}(G)<\#\text{Aut}(G\prime )$.

By the discussion above, it is sufficient to show the inequality in Proposition 2 for G with the following additional condition:

• G is loopless and bridgeless.

Furthermore, for such G, it is sufficient to show that equality ($\star$) holds only if G is one of the graphs in (A) and (B). In what follows, we suppose that G is loopless and bridgeless.

Let d be the maximum degree of the vertices of G and let l be the number of vertices of G of degree d. Since $g\ge 2$, we have $d\ge 3$. Furthermore, by the hand-shaking lemma, we have $$2\#E_G\ge dl+2(\#V_G-l),$$ and hence $$\begin{array}{c}g=\#E_G-\#V_G+1\\ \ge \frac{dl}{2}+\#V_G-l-\#V_G+1\\ =\left(\frac{d}{2}-1\right)l+1.\end{array}$$

As $d\ge 3$, we have $l\le 2g-2$.

Let $x_1,\dots ,x_l$ be all the vertices of G of degree d. Set x = x₁. If l = 1, then $\text{Aut}(G)=\text{Aut}{(G)}_x$ holds and the assertion follows from Proposition 6 and Remark 8. In what follows, we assume $l\ge 2$, and in particular, $g\ge d-1$. The group homomorphism $$s:\text{Aut}(G)\to S_l=S\{x_1,\dots ,x_l\};\hspace{1em}f\mapsto \left(\begin{array}{cccc}{x}_1& x_2& \cdots & x_l\\ f(x_1)& f(x_2)& \cdots & f(x_l)\end{array}\right)$$ induces an injective map on the left cosets $$\left\{f\text{Aut}{(G)}_x\right|f\in \text{Aut}(G)\}\mathrm{}\to \mathrm{}\{\sigma S\{x_2,\dots ,x_l\}|\sigma \in S\{x_1,\dots ,x_l\left\}\right\}.$$

Therefore we have $$\#\text{Aut}(G)\le l·\#\text{Aut}{(G)}_x.$$

Let $G\setminus \left\{x\right\}=U_1\bigsqcup \cdots \bigsqcup U_k$ be the decomposition to the connected components of $G\setminus \left\{x\right\}$. Let $G_i=U_i\cup \left\{x\right\}$ be the subgraph of G, and let g_i be the Betti number of G_i . Then $g={\sum }_{i=1}^k{g}_i$ and $g_i\ge 1$ hold. Furthermore, each G_i is loopless since G is bridgeless.

We deal with two cases where k = 1 and where $k\ge 2$ separately.

Case 1 Suppose k = 1.

Case 1-1 Suppose $d=g+1$. Then we have $$g\ge \left(\frac{d}{2}-1\right)l+1=g+\left(\frac{l}{2}-1\right)(g-1).$$

Therefore, we have l = 2 since $g\ge 2$ and $l\ge 2$. By Claim 7, we have $$\#\text{Aut}(G)\le l·\#\text{Aut}{(G)}_x\le 2d!=2·(g+1)!.$$

Here, we note that d equals the number of the edges incident to x since G is loopless.

When $g\ge 3$, we have $2·(g+1)!\le 2^{g}g!$ and get the desired inequality $\#\text{Aut}(G)\le 2^{g}g!$. We note that the equality $\#\text{Aut}(G)=2^{g}g!$ holds only if $(g,d,l)=(3,4,2)$. Under the assumption that k = 1, only subdivisions of $G_{\text{banana},3}$ may satisfy $(g,d,l)=(3,4,2)$. Hence G must be one of the graphs in (A) with g = 3 if $\#\text{Aut}(G)=48=2^{g}g!$ hold.

When g = 2, we have d = 3. In this case, since G is bridgeless, G is a subdivision of $G_{\text{banana},2}$ and we have $\#\text{Aut}(G)\le 12=2^{g}g!$. The equality $\#\text{Aut}(G)=12$ holds if and only if G is one of the graphs in (A) with g = 2.

Case 1-2 Suppose $d<g+1$. By Claim 7, we have $$\begin{array}{c}\#\text{Aut}(G)\le l·\#\text{Aut}{(G)}_x\\ \le l·2^{g-d+1}d!(g-d+1)!\\ \le (2g-2)2^{g-d+1}d!(g-d+1)!.\end{array}$$

Thus, it is sufficient to show that $$d!(g-d+1)!(2g-2)\le 2^{d-1}g!.$$

If $g-d+1=1$, then the inequality is equivalent to $g-1\le 2^{g-2}$ and it holds since $g=d\ge 3$. Therefore we get the desired inequality $\#\text{Aut}(G)\le 2^{g}g!$. We note that the equality $\#\text{Aut}(G)=2^{g}g!$ holds only if g and l satisfy $$l=2g-2,\hspace{1em}g-1=2^{g-2}.$$

Since $g=d\ge 3,(g,d,l)=(3,3,4)$ is the only case. In this case, G is one of the following graphs.

• A subdivision of H₁ in Figure 2.

• A subdivision of H₂ in Figure 2.

Fig. 1 The left graph is $G_{\text{banana},2}$, the center graph is $G_{\text{bouquet},3}$ and the right graph is $G_{\text{lollipop},4}$. Black dots (resp. lines) stand for vertices (resp. edges).

Fig. 2 We call the left graph H₁ and the right graph H₂. Black dots (resp. lines) stand for vertices (resp. edges).

We have $\#\text{Aut}(G)\le \#\text{Aut}(H_1)=4!<2^{g}g!$ in the former case, and $\#\text{Aut}(G)\le \#\text{Aut}(H_2)=16<2^{g}g!$ in the latter case. Therefore, the equality $\#\text{Aut}(G)=2^{g}g!$ never holds in this case.

If $g-d+1\ge 2$, we have $$\begin{array}{c}\frac{2^{d-1}}{2g-2}·\frac{g!}{d!(g-d+1)!}\ge \frac{4}{2g-2}·\frac{g!}{d!(g-d+1)!}\\ =\frac{2}{(g+1)(g-1)}\left(\begin{array}{c}g+1\\ d\end{array}\right)\\ >1.\end{array}$$

Here the first inequality follows because $d\ge 3$. The second inequality follows from the fact that $$\left(\begin{array}{c}g+1\\ d\end{array}\right)\ge \left(\begin{array}{c}g+1\\ 2\end{array}\right)=\frac{(g+1)g}{2}>\frac{(g+1)(g-1)}{2},$$ which is obtained by $d\ge 2$ and $g-d+1\ge 2$. Therefore we get the strict inequality $\#\text{Aut}(G)<2^{g}g!$ in this case.

Case 2 Suppose $k\ge 2$.

First, we see that $d\ge 4$, and especially $2\le l\le g-1$. Suppose the contrary that d = 3. Let e₁, e₂, and e₃ be the edges incident to x. As $k\ge 2$, there exists G_i such that $E_{G_i}$ contains just one of e₁, e₂, and e₃. Such an edge should be a bridge, a contradiction.

Let t denote the group homomorphism $$\begin{array}{c}t:\text{Aut}{(G)}_x\to S_k=S\{G_1,\dots ,G_k\};\\ f\mapsto \left(\begin{array}{cccc}{G}_1& G_2& \cdots & G_k\\ f(G_1)& f(G_2)& \cdots & f(G_k)\end{array}\right).\end{array}$$

Then, we have $$\begin{array}{c}\#\text{Aut}{(G)}_x=\#\text{Im}(t)·\#\text{Ker}(t)\\ \le \#\text{Im}(t)·\#\text{Aut}{(G_1)}_x\cdots \#\text{Aut}{(G_k)}_x.\end{array}$$

Hence, by Proposition 6, we have $$\begin{array}{c}\#\text{Aut}(G)\le l·\#\text{Aut}{(G)}_x\\ \le l·\#\text{Im}(t)·(2^{g_1}{g}_1!)\cdots (2^{g_k}{g}_k!)\\ =l·\#\text{Im}(t)·2^g·(g_1!)\cdots (g_k!).\end{array}$$

Case 2-1 Suppose that $g_1=g_2=\cdots =g_k$ does not hold.

Since $f\in \text{Aut}(G)$ maps G_i to only G_j such that g_i = g_j , we have $\#\text{Im}(t)\le (k-1)!$ in this case. Then we have $$\begin{array}{c}l·\#\text{Im}(t)·(g_1!)\cdots (g_k!)\le (g-1)(k-1)!(g_1!)(g_2!)\cdots (g_k!)\\ \le (g-1)(g-1)!\\ <g!.\end{array}$$

Here the second inequality follows from Lemma 5. Therefore we get the strict inequality $\#\text{Aut}(G)<2^{g}g!$ in this case.

Case 2-2 Suppose that $k\ge 3$ and $g_1=g_2=\cdots =g_k$.

Suppose that x is fixed for any $f\in \text{Aut}(G)$. Then $\text{Aut}(G)=\text{Aut}{(G)}_x$ holds and the assertion follows from Proposition 6 and Remark 8. Therefore we may assume that $f(x)\cancel{=}x$ for some $f\in \text{Aut}(G)$. We set $x^{\prime }=f(x)$. Let $$G\setminus \left\{x^{\prime }\right\}=U_1^{\prime }\bigsqcup \cdots \bigsqcup U_{k^{\prime }}^{\prime }$$ be the decomposition to the connected components of $G\setminus \left\{x^{\prime }\right\}$. Let $G_i^{\prime }=U_i^{\prime }\cup \left\{x^{\prime }\right\}$ be the subgraph of G, and let $g_i^{\prime }$ be its Betti number. Since the automorphism f maps x to $x^{\prime }$, $k^{\prime }$ must be k and $g{\prime }_i=g/k$ holds for each i. We may assume that $x^{\prime }\in V_{G_1}$. Suppose $x\in V_{G_i^{\prime }}$. Then $G_2,\dots ,G_k$ are subgraphs of $G_i^{\prime }$. Therefore it follows that $$\frac{k-1}{k}g=g_2+\cdots +g_k\le g_i^{\prime }=\frac{g}{k},$$ and contradicts the assumption $k\ge 3$.

Case 2-3 Suppose that k = 2 and g₁ = g₂.

Let $g^{\prime }:=g_1=g_2$. Since $l\le g-1=2g^{\prime }-1$, we have $$l·\#\text{Im}(t)·{(g^{\prime }!)}^2\le (2g^{\prime }-1)·2·{(g^{\prime }!)}^2\le (2g^{\prime })!=g!,$$

which proves the desired inequality $\#\text{Aut}(G)\le 2^{g}g!$. We note that the equality $\#\text{Aut}(G)=2^{g}g!$ holds only if $g\prime$ and l satisfy $$l=2g\prime -1,\hspace{1em}(2g^{\prime }-1)·2·{(g^{\prime }!)}^2=(2g^{\prime })!.$$

Since $2g\prime =g\ge 3$, we have $(g\prime ,g,d,l)=(2,4,4,3)$. We note that such G has no vertices of degree three by the hand-shaking lemma. Therefore, in this case, G turns out to be a subdivision of the graph H in Figure 3. Hence we have $\#\text{Aut}(G)\le \#\text{Aut}(H)=2^5<2^{g}g!$, and the equality $\#\text{Aut}(G)=2^{g}g!$ never holds in this case. □

Fig. 3 We call the graph H. Black dots (resp. lines) stand for vertices (resp. edges).

Finally, we shall prove Theorem 1.

Proof of Theorem 1.

Let V be the set of all points of $\Gamma$ except for two-valent points. We add to V all midpoints of loops. Let (G, l) be the pair defining $\Gamma$ that has the added set V as its set of vertices. Each $f\in \text{Aut}(\Gamma )$ induces a permutation of the subset of $\Gamma$ corresponding to V_G and that of the set of intervals of $\Gamma$ corresponding to edges of G. This induces a group homomorphism $\text{Aut}(\Gamma )\to \text{Aut}(G)$. Since G is loopless, it is injective. Then we have $$\#\text{Aut}(\Gamma )\le \#\text{Aut}(G).$$

By Proposition 2, we have the desired inequality.

In each case of equality conditions of Theorem 1, clearly, the inequality becomes an equality. The converse follows from Proposition 2 and the fact that each $f\in \text{Aut}(@@\Gamma )$ is an isometry $\Gamma \to \Gamma$. □

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

The first author is partially supported by JSPS KAKENHI Grant Number 18K13384. The second author is supported by JSPS KAKENHI Grant Number 20J11910.