# Vertex links and the Grushko decomposition

Suraj Krishna Meda Satish

► To cite this version:

Suraj Krishna Meda Satish. Vertex links and the Grushko decomposition. Annales de la Faculté des Sciences de Toulouse. Mathématiques., 2023, 32 (3), pp.555-576. 10.5802/afst.1744. hal-03525600

HAL Id: hal-03525600

https://hal.science/hal-03525600

Submitted on 23 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

HAL
open science

# Vertex links and the Grushko decomposition

Suraj Krishna Meda Satish

► To cite this version:

Suraj Krishna Meda Satish. Vertex links and the Grushko decomposition. Annales de la Faculté des Sciences de Toulouse. Mathématiques., 2023, 32 (3), pp.555-576. 10.5802/afst.1744. hal-03525600

HAL Id: hal-03525600

https://hal.science/hal-03525600v1

Submitted on 23 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
ANNALES

DE LA FACULTÉ
DES SCIENCES

DE
TOULOUSE
Mathématiques

SURAJ KRISHNA M S.

Vertex links and the Grushko decomposition

Tome XXXII, n° 3 (2023), p. 555–576.

https://doi.org/10.5802/afst.1744

© les auteurs, 2023.

Les articles des *Annales de la Faculté des Sciences de Toulouse* sont mis
à disposition sous la license Creative Commons Attribution (CC-BY) 4.0
http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_2.png" /></figure>

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>
ANNALES

DE LA FACULTÉ
DES SCIENCES

DE
TOULOUSE

Mathématiques

SURAJ KRISHNA M S.

Vertex links and the Grushko decomposition

Tome XXXII, n° 3 (2023), p. 555–576.

https://doi.org/10.5802/afst.1744

© les auteurs, 2023.

Les articles des *Annales de la Faculté des Sciences de Toulouse* sont mis à disposition sous la license Creative Commons Attribution (CC-BY) 4.0 http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>
# Vertex links and the Grushko decomposition (*)

SURAJ KRISHNA M S. (1)

**ABSTRACT.** — We develop an algorithm of polynomial time complexity to construct the Grushko decomposition of fundamental groups of graphs of free groups with cyclic edge groups. Our methods rely on analysing vertex links of certain CAT(0) square complexes naturally associated with a special class of the above groups. Our main result transforms a one-ended CAT(0) square complex of the above type to one whose vertex links satisfy a strong connectivity condition, as first studied by Brady and Meier.

**RÉSUMÉ.** — Nous développons un algorithme polynomial pour construire la décomposition de Grushko du groupe fondamental d'un graphe de groupes libres à sous-groupes d'arêtes cycliques. Notre méthode repose sur l'analyse du link des sommets d'un complexe carré naturellement associé à une classe spéciale des groupes ci-dessus. Notre résultat principal transforme un complexe carré CAT(0) avec un seul bout en un autre dont le link des sommets vérifie une condition de connectivité forte, étudiée pour la première fois par Brady et Meier.

## 1. Introduction

The Grushko decomposition theorem [8] states that a finitely generated group is a free product of finitely many freely indecomposable non-free groups and a finite rank free group. This decomposition is unique in the sense that the freely indecomposable groups appearing in this decomposition are unique up to reordering and conjugation, and the rank of the free group is invariant.

**Keywords:** Free splittings, CAT(0) cube complexes, ends of groups, graphs of groups, Grushko decomposition.

2020 Mathematics Subject Classification: 20F65, 20F67, 20E06, 20E08.

Article proposé par Jean-Pierre Otal.

<footnote>(*) Reçu le 22 août 2020, accepté le 18 juin 2021.</footnote>

<footnote>(1) Tata Institute of Fundamental Research, School of Mathematics, Mumbai 400005, India — Current address: Faculty of Mathematics, Technion — Israel institute of Technology, Haifa, Israel — surajms@campus.technion.ac.il</footnote>
# Vertex links and the Grushko decomposition (*)

SURAJ KRISHNA M S. (1)

**ABSTRACT.** — We develop an algorithm of polynomial time complexity to construct the Grushko decomposition of fundamental groups of graphs of free groups with cyclic edge groups. Our methods rely on analysing vertex links of certain CAT(0) square complexes naturally associated with a special class of the above groups. Our main result transforms a one-ended CAT(0) square complex of the above type to one whose vertex links satisfy a strong connectivity condition, as first studied by Brady and Meier.

**RÉSUMÉ.** — Nous développons un algorithme polynomial pour construire la décomposition de Grushko du groupe fondamental d'un graphe de groupes libres à sous-groupes d'arêtes cycliques. Notre méthode repose sur l'analyse du link des sommets d'un complexe carré naturellement associé à une classe spéciale des groupes ci-dessus. Notre résultat principal transforme un complexe carré CAT(0) avec un seul bout en un autre dont le link des sommets vérifie une condition de connectivité forte, étudiée pour la première fois par Brady et Meier.

## 1. Introduction

The Grushko decomposition theorem [8] states that a finitely generated group is a free product of finitely many freely indecomposable non-free groups and a finite rank free group. This decomposition is unique in the sense that the freely indecomposable groups appearing in this decomposition are unique up to reordering and conjugation, and the rank of the free group is invariant.

<footnote>(*) Reçu le 22 août 2020, accepté le 18 juin 2021.</footnote>

<footnote>Keywords: Free splittings, CAT(0) cube complexes, ends of groups, graphs of groups, Grushko decomposition.</footnote>

<footnote n="2020">2020 Mathematics Subject Classification: 20F65, 20F67, 20E06, 20E08.</footnote>

<footnote>(1) Tata Institute of Fundamental Research, School of Mathematics, Mumbai 400005, India — Current address: Faculty of Mathematics, Technion — Israel institute of Technology, Haifa, Israel — surajms@campus.technion.ac.il</footnote>

<footnote>Article proposé par Jean-Pierre Otal.</footnote>
Given a finitely presented group, there is no algorithm in general to compute its Grushko decomposition. Even when algorithms do exist, they are often not tractable. In this article, we develop an algorithm, with polynomial time complexity, to compute the Grushko decomposition of fundamental groups of graphs of free groups with cyclic edge groups (see Theorem B).

Our algorithm is obtained as a consequence of Corollary 1.3, which gives an algorithm to obtain the Grushko decomposition of fundamental groups of compact nonpositively curved square complexes that we call *tubular graphs of graphs*. A tubular graph of graphs (see Definition 2.8 for the precise definition) is a square complex obtained by attaching finitely many tubes (a *tube* is the Cartesian product of a circle and the unit interval) to a finite collection of finite graphs. Tubular graphs of graphs are thus nonpositively curved *VH*-complexes (in the sense of Wise [24]) in which vertical hyperplanes are homeomorphic to circles (see Section 2).

In [20], Stallings built on work by Whitehead [22] and developed an algorithm that takes a free group and finitely many cyclic subgroups as input and decides whether or not the free group splits freely relative to the cyclic subgroups. We use the machinery of tubular graphs of graphs in this article to develop an alternative algorithm.

In fact, we also obtain an analogue for tubular graphs of graphs of a result by Jaco [11] in 3-manifold theory which states that if the fundamental group of a 3-manifold splits as a free product, then each free factor is itself the fundamental group of a 3-manifold.

Our approach is geometric and in fact we are more interested in nonpositively curved square complexes than groups. We show how to construct the Grushko decomposition by cutting along contractible subspaces of tubular graphs of graphs which induce free splittings.

Crucial to our methods is the following key result by Brady and Meier:

**THEOREM 1.1 ([1]).** — Let $X$ be a finite connected nonpositively curved cube complex. Suppose that

(BM1) for each vertex $v \in X$, the link of $v$ is connected and

(BM2) for each vertex $v \in X$ and each simplex $\sigma$ in $\text{link}(v)$, $\text{link}(v) \setminus \sigma$ is (non-empty and) connected.

Then $\tilde{X}$ is one-ended.

We say that a cube complex is *Brady–Meier* if it satisfies the conditions (BM1) and (BM2) above. Note that the Brady–Meier conditions are local and hence preserved by covering maps. The converse of Theorem 1.1 is not
Given a finitely presented group, there is no algorithm in general to compute its Grushko decomposition. Even when algorithms do exist, they are often not tractable. In this article, we develop an algorithm, with polynomial time complexity, to compute the Grushko decomposition of fundamental groups of graphs of free groups with cyclic edge groups (see Theorem B).

Our algorithm is obtained as a consequence of Corollary 1.3, which gives an algorithm to obtain the Grushko decomposition of fundamental groups of compact nonpositively curved square complexes that we call *tubular graphs of graphs*. A tubular graph of graphs (see Definition 2.8 for the precise definition) is a square complex obtained by attaching finitely many tubes (a *tube* is the Cartesian product of a circle and the unit interval) to a finite collection of finite graphs. Tubular graphs of graphs are thus nonpositively curved *VH*-complexes (in the sense of Wise [24]) in which vertical hyperplanes are homeomorphic to circles (see Section 2).

In [20], Stallings built on work by Whitehead [22] and developed an algorithm that takes a free group and finitely many cyclic subgroups as input and decides whether or not the free group splits freely relative to the cyclic subgroups. We use the machinery of tubular graphs of graphs in this article to develop an alternative algorithm.

In fact, we also obtain an analogue for tubular graphs of graphs of a result by Jaco [11] in 3-manifold theory which states that if the fundamental group of a 3-manifold splits as a free product, then each free factor is itself the fundamental group of a 3-manifold.

Our approach is geometric and in fact we are more interested in nonpositively curved square complexes than groups. We show how to construct the Grushko decomposition by cutting along contractible subspaces of tubular graphs of graphs which induce free splittings.

Crucial to our methods is the following key result by Brady and Meier:

**THEOREM 1.1 ([1]).** — Let $X$ be a finite connected nonpositively curved cube complex. Suppose that

(BM1) for each vertex $v \in X$, the link of $v$ is connected and

(BM2) for each vertex $v \in X$ and each simplex $\sigma$ in $\text{link}(v)$, $\text{link}(v) \setminus \sigma$ is (non-empty and) connected.

Then $\tilde{X}$ is one-ended.

We say that a cube complex is *Brady–Meier* if it satisfies the conditions (BM1) and (BM2) above. Note that the Brady–Meier conditions are local and hence preserved by covering maps. The converse of Theorem 1.1 is not
true in general. The main result of the article gives a geometric/combinatorial
procedure that modifies a given tubular graph of graphs to a homotopy
equivalent tubular graph of graphs which is Brady-Meier if and only if the
fundamental group is one-ended:

**THEOREM A (Theorem 5.3).** — *There is an algorithm of polynomial time complexity which takes a tubular graph of graphs as input and returns a homotopy equivalent tubular graph of graphs which is either a Brady-Meier complex or contains a locally disconnecting vertex which splits the fundamental group as a free product.*

For this and the corollaries below, the running times of the algorithms are
polynomial in the number of squares of the input square complex. A major
application of the above theorem is in the development of an algorithm to
obtain the JSJ decomposition of one-ended hyperbolic fundamental groups
of tubular graphs of graphs [13]. The main point is that one can work with
a Brady-Meier tubular graph of graphs (obtained in polynomial time) when
the fundamental group is one-ended, thanks to Theorem A.

The key step in the construction of our algorithm involves a simplification
of the input tubular graph of graphs by “opening-up” at a vertex which does
not satisfy (BM2). This opening-up keeps the number of squares in the
complex constant, while simplifying certain vertex links. We call such an
opening procedure as an *SL-move* (“SL” stands for simplified link). We thus
obtain a partial converse to Theorem 1.1:

**COROLLARY 1.2.** — *A tubular graph of graphs has a one-ended universal cover if and only if it can be simplified in finitely many SL-moves to a Brady-Meier tubular graph of graphs with isomorphic fundamental group.*

We also obtain the Grushko decomposition of these groups using Theo-
rem A. In fact, we obtain a stronger result:

**COROLLARY 1.3 (Corollary 5.4).** — *There is an algorithm of polynomial time complexity which takes as input a tubular graph of graphs and returns a homotopy equivalent tubular graph of graphs obtained by gluing together certain vertices of a finite collection of Brady-Meier tubular graphs of graphs and finite graphs. Further, the free product decomposition induced by cutting along the glued vertices is the Grushko decomposition of the fundamental group of the input tubular graph of graphs.*

We point out that our proof neither uses Stallings' theorem on ends of
finitely generated groups nor assumes the existence of a Grushko decompo-
sition. In fact, our procedure yields a new proof of Stallings' theorem for
true in general. The main result of the article gives a geometric/combinatorial
procedure that modifies a given tubular graph of graphs to a homotopy
equivalent tubular graph of graphs which is Brady-Meier if and only if the
fundamental group is one-ended:

**THEOREM A (Theorem 5.3).** — There is an algorithm of polynomial time complexity which takes a tubular graph of graphs as input and returns a homotopy equivalent tubular graph of graphs which is either a Brady-Meier complex or contains a locally disconnecting vertex which splits the fundamental group as a free product.

For this and the corollaries below, the running times of the algorithms are
polynomial in the number of squares of the input square complex. A major
application of the above theorem is in the development of an algorithm to
obtain the JSJ decomposition of one-ended hyperbolic fundamental groups
of tubular graphs of graphs [13]. The main point is that one can work with
a Brady-Meier tubular graph of graphs (obtained in polynomial time) when
the fundamental group is one-ended, thanks to Theorem A.

The key step in the construction of our algorithm involves a simplification
of the input tubular graph of graphs by “opening-up” at a vertex which does
not satisfy (BM2). This opening-up keeps the number of squares in the
complex constant, while simplifying certain vertex links. We call such an
opening procedure as an *SL-move* (“SL” stands for simplified link). We thus
obtain a partial converse to Theorem 1.1:

**COROLLARY 1.2.** — *A tubular graph of graphs has a one-ended universal cover if and only if it can be simplified in finitely many SL-moves to a Brady-Meier tubular graph of graphs with isomorphic fundamental group.*

We also obtain the Grushko decomposition of these groups using Theo-
rem A. In fact, we obtain a stronger result:

**COROLLARY 1.3 (Corollary 5.4).** — There is an algorithm of polynomial time complexity which takes as input a tubular graph of graphs and returns a homotopy equivalent tubular graph of graphs obtained by gluing together certain vertices of a finite collection of Brady-Meier tubular graphs of graphs and finite graphs. Further, the free product decomposition induced by cutting along the glued vertices is the Grushko decomposition of the fundamental group of the input tubular graph of graphs.

We point out that our proof neither uses Stallings' theorem on ends of
finitely generated groups nor assumes the existence of a Grushko decompo-
sition. In fact, our procedure yields a new proof of Stallings' theorem for
fundamental groups of tubular graphs of graphs as well as the existence of
a Grushko decomposition for these groups.

The analogue of Jaco's result immediately follows:

COROLLARY 1.4 (Corollary 5.6). — Let $X$ be a tubular graph of graphs with fundamental group $G$. If $G = A * B$, then there exist tubular graphs of graphs $X_1$ and $X_2$ such that $A$ and $B$ are fundamental groups of $X_1$ and $X_2$ respectively. Moreover, $X_1$ and $X_2$ can be so chosen such that the total number of squares in $X_1$ and $X_2$ is bounded by the number of squares in $X$.

The Grushko decomposition may be found algorithmically in other situ-
ations. Jaco, Letscher and Rubinstein [12] gave an algorithm of polynomial
time complexity to compute the prime decomposition of a 3-manifold from
a triangulation. Gerasimov [6] showed that the Grushko decomposition can
be computed for hyperbolic groups. But there is no known bound on the
complexity of his algorithm. Dahmani and Groves [3] extended Gerasimov's
ideas to groups which are hyperbolic relative to abelian subgroups. Diao
and Feighn [4] gave an algorithm for graphs of free groups. Their algorithm
relies on certain simplifications of a given graph of free groups which de-
pend on finding Gersten representatives of the incident edge groups in each
vertex group, which is algorithmic. More recently, Touikan [21] presented
an important algorithm which returns the Grushko decomposition of finitely
presented groups with solvable word problem and no 2-torsion. However, the
time complexity of his algorithm is not known.

We note that our algorithm is explicit and neither uses the Rips machine
nor requires solutions of equations in free groups, as some of the above
algorithms do.

We mention another application of our algorithm, before stating our re-
sult for general graphs of free groups with cyclic edge groups. As defined
by Stallings in [20], a finite set of words $W$ of a finite rank free group $F$ is
*separable* if there exists a nontrivial free splitting of $F$ such that each word
of $W$ conjugates into a free factor.

Stallings obtained an algorithm to detect separability in [20]. In a related
result, Roig, Ventura and Weil [15] obtained a polynomial time algorithm
to solve the Whitehead minimization problem and therefore the primitivity
problem. We give an alternate version of Stallings' algorithm using Theo-
rem A:

COROLLARY 1.5 (Corollary 6.2). — There exists an algorithm of poly-
nomial time complexity that takes a finite set of words in a finite rank free
group as input and decides whether it is separable.
fundamental groups of tubular graphs of graphs as well as the existence of
a Grushko decomposition for these groups.

The analogue of Jaco's result immediately follows:

COROLLARY 1.4 (Corollary 5.6). — Let $X$ be a tubular graph of graphs with fundamental group $G$. If $G = A * B$, then there exist tubular graphs of graphs $X_1$ and $X_2$ such that $A$ and $B$ are fundamental groups of $X_1$ and $X_2$ respectively. Moreover, $X_1$ and $X_2$ can be so chosen such that the total number of squares in $X_1$ and $X_2$ is bounded by the number of squares in $X$.

The Grushko decomposition may be found algorithmically in other situ-
ations. Jaco, Letscher and Rubinstein [12] gave an algorithm of polynomial
time complexity to compute the prime decomposition of a 3-manifold from
a triangulation. Gerasimov [6] showed that the Grushko decomposition can
be computed for hyperbolic groups. But there is no known bound on the
complexity of his algorithm. Dahmani and Groves [3] extended Gerasimov's
ideas to groups which are hyperbolic relative to abelian subgroups. Diao
and Feighn [4] gave an algorithm for graphs of free groups. Their algorithm
relies on certain simplifications of a given graph of free groups which de-
pend on finding Gersten representatives of the incident edge groups in each
vertex group, which is algorithmic. More recently, Touikan [21] presented
an important algorithm which returns the Grushko decomposition of finitely
presented groups with solvable word problem and no 2-torsion. However, the
time complexity of his algorithm is not known.

We note that our algorithm is explicit and neither uses the Rips machine
nor requires solutions of equations in free groups, as some of the above
algorithms do.

We mention another application of our algorithm, before stating our re-
sult for general graphs of free groups with cyclic edge groups. As defined
by Stallings in [20], a finite set of words $W$ of a finite rank free group $F$ is
*separable* if there exists a nontrivial free splitting of $F$ such that each word
of $W$ conjugates into a free factor.

Stallings obtained an algorithm to detect separability in [20]. In a related
result, Roig, Ventura and Weil [15] obtained a polynomial time algorithm
to solve the Whitehead minimization problem and therefore the primitivity
problem. We give an alternate version of Stallings’ algorithm using Theo-
rem A:

COROLLARY 1.5 (Corollary 6.2). — There exists an algorithm of poly-
nomial time complexity that takes a finite set of words in a finite rank free
group as input and decides whether it is separable.
Stallings obtains his algorithm by constructing a Whitehead graph for the given set of words in a chosen basis. He then uses a Whitehead automorphism to modify the basis whenever there is a cut vertex in the Whitehead graph to reduce the total length of the given set of words. We first give a new proof of Whitehead's cut vertex theorem (Proposition 6.4). We then obtain our algorithm by first constructing the tubular graph of graphs associated to a "double" of the free group with the given set of words. We then apply the algorithm of Theorem A.

By combining a result of Wilton [23] (see Theorem 6.7) with Corollary 1.3, we obtain the advertised result:

**THEOREM B (Theorem 7.1).** — There exists an algorithm of polynomial time complexity which takes a graph of free groups with cyclic edge groups as input and returns as output the Grushko decomposition of its fundamental group.

The running time of the algorithm is polynomial in the sum of the lengths of the words induced by the generators of the edge groups in the respective vertex groups.

## Acknowledgements

I thank my advisors Frédéric Haglund and Thomas Delzant for suggesting the problem and for several important discussions. Part of this work was done when I was visiting IRMA, Strasbourg. This work was supported by a French public grant for research, as part of the Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH. I am grateful to the referee for their suggestions to improve the paper.

## 2. The setup

### 2.1. $VH$-complexes

The notion of $VH$-complexes was first introduced in [24].

**DEFINITION 2.1.** — A square complex is a two dimensional CW complex in which each 2-cell is attached to a combinatorial loop of length 4 and is isometric to the standard Euclidean unit square $I^2 = [0, 1]^2$.

All our square complexes will be locally finite.
Stallings obtains his algorithm by constructing a Whitehead graph for the given set of words in a chosen basis. He then uses a Whitehead automorphism to modify the basis whenever there is a cut vertex in the Whitehead graph to reduce the total length of the given set of words. We first give a new proof of Whitehead's cut vertex theorem (Proposition 6.4). We then obtain our algorithm by first constructing the tubular graph of graphs associated to a "double" of the free group with the given set of words. We then apply the algorithm of Theorem A.

By combining a result of Wilton [23] (see Theorem 6.7) with Corollary 1.3, we obtain the advertised result:

**THEOREM B** (Theorem 7.1). — There exists an algorithm of polynomial time complexity which takes a graph of free groups with cyclic edge groups as input and returns as output the Grushko decomposition of its fundamental group.

The running time of the algorithm is polynomial in the sum of the lengths of the words induced by the generators of the edge groups in the respective vertex groups.

## Acknowledgements

I thank my advisors Frédéric Haglund and Thomas Delzant for suggesting the problem and for several important discussions. Part of this work was done when I was visiting IRMA, Strasbourg. This work was supported by a French public grant for research, as part of the Investissement d'avenir project, reference ANR-11-LABX-0056-LMH, LabEx LMH. I am grateful to the referee for their suggestions to improve the paper.

## 2. The setup

### 2.1. $VH$-complexes

The notion of $VH$-complexes was first introduced in [24].

**DEFINITION 2.1.** — A square complex is a two dimensional CW complex in which each 2-cell is attached to a combinatorial loop of length 4 and is isometric to the standard Euclidean unit square $I^2 = [0, 1]^2$.

All our square complexes will be locally finite.
**DEFINITION 2.2 (Vertex links).** — Let $v \in X$ be a vertex of a square complex. The link of $v$, denoted by $link(v)$ is a graph whose vertex set is the set $\{e \mid e \text{ is a half-edge incident to } v\}$. The number of edges between two vertices $e, f$ is the number of squares of $X$ in which $e, f$ are adjacent half-edges.

**DEFINITION 2.3.** — A square complex is nonpositively curved if the length of a closed path in the link of any of its vertices is at least four.

By a result of Gromov [7], a simply connected nonpositively curved square complex is CAT(0) in the metric sense.

**DEFINITION 2.4 ([16]).** — Let $X$ be a square complex. A mid-edge of a square $s$ in $X$ is an edge (after subdivision of $s$) running through the center of $s$ and parallel to two of the edges of $s$. Declare two edges $e$ and $f$ to be equivalent if there exists a sequence $e = e_1, \dots, e_n = f$ of edges such that $e_i$ and $e_{i+1}$ are opposite edges of some square of $X$. Given an equivalence class $[e]$ of edges, the hyperplane dual to $e$, denoted by $h_e$, is the collection of mid-edges which intersect edges in $[e]$.

**DEFINITION 2.5 ([24]).** — A $\mathcal{V}\mathcal{H}$-complex is a square complex in which every 1-cell is labelled as either vertical or horizontal in such a way that each 2-cell is attached to a loop which alternates between horizontal and vertical 1-cells.

The labelling of the edges of a $\mathcal{V}\mathcal{H}$-complex as horizontal and vertical induces a labelling of the vertices in the link of any vertex as horizontal and vertical, thus making the link a bipartite graph. Similarly, the hyperplanes of a $\mathcal{V}\mathcal{H}$ complex are also labelled as vertical and horizontal, with a vertical hyperplane being dual to an equivalence class of horizontal edges and a horizontal hyperplane being dual to an equivalence class of vertical edges.

**Remark 2.6.** — Since the link of any vertex of a $\mathcal{V}\mathcal{H}$-complex is bipartite, the length of a closed path is even. Thus a $\mathcal{V}\mathcal{H}$-complex is nonpositively curved if there exists no bigon in any vertex link.

## 2.2. Graphs of spaces

Graphs of groups are the basic objects of study in Bass-Serre theory [18]. It was studied from a topological perspective in [17] by looking at graphs of spaces instead of graphs of groups. We will adopt this point of view.

**DEFINITION 2.7.** — By a graph of spaces, we mean the following data: $\Gamma$ is a connected graph, called the underlying graph. For each vertex $s$ (edge $a$)
**DEFINITION 2.2 (Vertex links).** — Let $v \in X$ be a vertex of a square complex. The link of $v$, denoted by $link(v)$ is a graph whose vertex set is the set $\{e \mid e \text{ is a half-edge incident to } v\}$. The number of edges between two vertices $e, f$ is the number of squares of $X$ in which $e, f$ are adjacent half-edges.

**DEFINITION 2.3.** — A square complex is nonpositively curved if the length of a closed path in the link of any of its vertices is at least four.

By a result of Gromov [7], a simply connected nonpositively curved square complex is CAT(0) in the metric sense.

**DEFINITION 2.4 ([16]).** — Let $X$ be a square complex. A mid-edge of a square $s$ in $X$ is an edge (after subdivision of $s$) running through the center of $s$ and parallel to two of the edges of $s$. Declare two edges $e$ and $f$ to be equivalent if there exists a sequence $e = e_1, \dots, e_n = f$ of edges such that $e_i$ and $e_{i+1}$ are opposite edges of some square of $X$. Given an equivalence class $[e]$ of edges, the hyperplane dual to $e$, denoted by $h_e$, is the collection of mid-edges which intersect edges in $[e]$.

**DEFINITION 2.5 ([24]).** — A $\mathcal{V}\mathcal{H}$-complex is a square complex in which every 1-cell is labelled as either vertical or horizontal in such a way that each 2-cell is attached to a loop which alternates between horizontal and vertical 1-cells.

The labelling of the edges of a $\mathcal{V}\mathcal{H}$-complex as horizontal and vertical induces a labelling of the vertices in the link of any vertex as horizontal and vertical, thus making the link a bipartite graph. Similarly, the hyperplanes of a $\mathcal{V}\mathcal{H}$ complex are also labelled as vertical and horizontal, with a vertical hyperplane being dual to an equivalence class of horizontal edges and a horizontal hyperplane being dual to an equivalence class of vertical edges.

**Remark 2.6.** — Since the link of any vertex of a $\mathcal{V}\mathcal{H}$-complex is bipartite, the length of a closed path is even. Thus a $\mathcal{V}\mathcal{H}$-complex is nonpositively curved if there exists no bigon in any vertex link.

## 2.2. Graphs of spaces

Graphs of groups are the basic objects of study in Bass–Serre theory [18]. It was studied from a topological perspective in [17] by looking at graphs of spaces instead of graphs of groups. We will adopt this point of view.

**DEFINITION 2.7.** — By a graph of spaces, we mean the following data: $\Gamma$ is a connected graph, called the underlying graph. For each vertex $s$ (edge $a$)
of $\Gamma$, $X_s (X_a)$ is a topological space. Further, whenever $a$ is incident to $s$, $\partial_{a,s} : X_a \to X_s$ is a $\pi_1$-injective continuous map. The geometric realisation of the above graph of spaces is the space $X = (\bigsqcup_{s \in \Gamma^{(0)}} X_s \sqcup \bigsqcup_{a \in \Gamma^{(1)}} X_a \times [0, 1])/\sim$, where $(x, 0)$ and $(x, 1)$ are identified respectively with $\partial_{a,s}(x)$ and $\partial_{a,s'}(x)$. Here, $s$ and $s'$ are the two endpoints of $a$.

Note that the universal cover of $X$ has the structure of a *tree of spaces*, a graph of spaces whose underlying graph is the Bass–Serre tree of the associated graph of groups structure of $X$ [17].

## 2.3. Tubular graphs of graphs

**DEFINITION 2.8.** — A tubular graph of graphs is a finite graph of spaces in which each vertex space is a finite connected simplicial graph and each edge space is a simplicial graph homeomorphic to a circle. Further, the attaching maps are simplicial immersions. We will always assume that the underlying graph is connected.

We note that no vertex graph is a tree, as a consequence of the definition. We also remark that asking for each vertex graph to be simplicial is not a serious restriction as every one dimensional CW complex is a simplicial graph after subdivision.

*Remark 2.9.* — Tubular graphs of graphs are topological versions of certain graphs of free groups with cyclic edge groups (see Section 7 for a definition). We note that any graph of free groups with cyclic edge groups in which the underlying graph is a tree can be realised topologically as a tubular graph of graphs. If the underlying graph contains a loop such that the generator of the edge group is attached to words of different lengths in the incident vertex group, then such a graph of free groups with cyclic edge groups cannot be realised as a tubular graph of graphs. In particular, this rules out non-Euclidean Baumslag–Solitar groups.

We also have

**PROPOSITION 2.10 ([24]).** — The geometric realisation of a tubular graph of graphs is a finite (hence compact), connected nonpositively curved $\mathcal{V}\mathcal{H}$-complex whose vertical hyperplanes are circles.

**CONVENTION.** — Throughout this text, we will use the same notation for a graph of graphs and the $\mathcal{V}\mathcal{H}$-complex which is its geometric realisation. $X$ will denote a tubular graph of graphs with underlying graph $\Gamma_X$. Let $s \in \Gamma_X$ be a vertex. Then $X_s$ will denote the vertex graph at $s$ and if $a$ is an edge
of $\Gamma$, $X_s (X_a)$ is a topological space. Further, whenever $a$ is incident to $s$, $\partial_{a,s} : X_a \to X_s$ is a $\pi_1$-injective continuous map. The geometric realisation of the above graph of spaces is the space $X = (\bigsqcup_{s \in \Gamma^{(0)}} X_s \sqcup \bigsqcup_{a \in \Gamma^{(1)}} X_a \times [0, 1])/\sim$, where $(x, 0)$ and $(x, 1)$ are identified respectively with $\partial_{a,s}(x)$ and $\partial_{a,s'}(x)$. Here, $s$ and $s'$ are the two endpoints of $a$.

Note that the universal cover of $X$ has the structure of a *tree of spaces*, a graph of spaces whose underlying graph is the Bass–Serre tree of the associated graph of groups structure of $X$ [17].

## 2.3. Tubular graphs of graphs

**DEFINITION 2.8.** — A tubular graph of graphs is a finite graph of spaces in which each vertex space is a finite connected simplicial graph and each edge space is a simplicial graph homeomorphic to a circle. Further, the attaching maps are simplicial immersions. We will always assume that the underlying graph is connected.

We note that no vertex graph is a tree, as a consequence of the definition. We also remark that asking for each vertex graph to be simplicial is not a serious restriction as every one dimensional CW complex is a simplicial graph after subdivision.

*Remark 2.9.* — Tubular graphs of graphs are topological versions of certain graphs of free groups with cyclic edge groups (see Section 7 for a definition). We note that any graph of free groups with cyclic edge groups in which the underlying graph is a tree can be realised topologically as a tubular graph of graphs. If the underlying graph contains a loop such that the generator of the edge group is attached to words of different lengths in the incident vertex group, then such a graph of free groups with cyclic edge groups cannot be realised as a tubular graph of graphs. In particular, this rules out non-Euclidean Baumslag–Solitar groups.

We also have

**PROPOSITION 2.10 ([24]).** — The geometric realisation of a tubular graph of graphs is a finite (hence compact), connected nonpositively curved $\mathcal{V}\mathcal{H}$-complex whose vertical hyperplanes are circles.

**CONVENTION.** — Throughout this text, we will use the same notation for a graph of graphs and the $\mathcal{V}\mathcal{H}$-complex which is its geometric realisation. $X$ will denote a tubular graph of graphs with underlying graph $\Gamma_X$. Let $s \in \Gamma_X$ be a vertex. Then $X_s$ will denote the vertex graph at $s$ and if $a$ is an edge
<figure><img src="image_5.png" /><figcaption>Figure 2.1. Removing rudimentary edges.</figcaption></figure>

of $\Gamma_X$, we will denote the edge graph at a by $X_a$. Thus, every edge of any vertex graph $X_s$ will be a vertical edge in the $V\mathcal{H}$-complex $X$ while horizontal edges in $X$ are the edges of the form $\{v\} \times [0, 1]$, for vertices $v$ in the edge graphs $X_a$.

**DEFINITION 2.11 (Thickness).** — For an edge $e$ in $X$, the thickness of $e$ is the number of squares of $X$ which contain $e$.

Observe that a horizontal edge of $X$ always has thickness equal to two.

**DEFINITION 2.12.** — Let $X_s$ be a vertex graph of a tubular graph of graphs $X$. We say that $X_s$ (and hence $X$) has a hanging tree if $X_s$ is a wedge of two subgraphs $A$ and $B$ such that one of them, say $A$, is a tree. Here, $A$ is called a hanging (sub)tree of $X_s$.

*Remark 2.13.* — Since the attaching maps of edge graphs are immersions, an edge in a hanging tree of $X$ has thickness zero.

We thus have that

**LEMMA 2.14.** — A tubular graph of graphs is homotopy equivalent to a tubular graph of graphs with no hanging trees.

**DEFINITION 2.15.** — An edge $e$ in $X_s$ is a rudimentary edge if it is of thickness one and moreover $X_s$ is a circle.

**LEMMA 2.16.** — A tubular graph of graphs is homotopically equivalent to a tubular graph of graphs with no rudimentary edges.

*Proof.* — Let $e$ be a rudimentary graph in a vertex graph $X_s$ of a tubular graph of graphs $X$. Since $X_s$ is a circle and attaching maps of edge graphs to $X_s$ are graph immersions, there exists exactly one edge $a$ incident to $s$ in the underlying graph $\Gamma_X$ and the attaching map from $X_a$ to $X_s$ is a graph isomorphism (see Figure 2.1).

Thus $X$ is homotopic to $X'$ obtained by removing $X_a$ and the open tube containing $X_a$. $\Gamma_{X'}$ is the graph obtained from $\Gamma_X$ by collapsing $a = (s, s')$ to $s'$. Repeating this procedure at each rudimentary edge gives the result. $\square$
<figure><img src="image_6.png" /><figcaption>Figure 2.1. Removing rudimentary edges.</figcaption></figure>

of $\Gamma_X$, we will denote the edge graph at a by $X_a$. Thus, every edge of any vertex graph $X_s$ will be a vertical edge in the $VH$-complex $X$ while horizontal edges in $X$ are the edges of the form $\{v\} \times [0, 1]$, for vertices $v$ in the edge graphs $X_a$.

**DEFINITION 2.11 (Thickness).** — For an edge $e$ in $X$, the thickness of $e$ is the number of squares of $X$ which contain $e$.

Observe that a horizontal edge of $X$ always has thickness equal to two.

**DEFINITION 2.12.** — Let $X_s$ be a vertex graph of a tubular graph of graphs $X$. We say that $X_s$ (and hence $X$) has a hanging tree if $X_s$ is a wedge of two subgraphs $A$ and $B$ such that one of them, say $A$, is a tree. Here, $A$ is called a hanging (sub)tree of $X_s$.

**Remark 2.13.** — Since the attaching maps of edge graphs are immersions, an edge in a hanging tree of $X$ has thickness zero.

We thus have that

**LEMMA 2.14.** — A tubular graph of graphs is homotopy equivalent to a tubular graph of graphs with no hanging trees.

**DEFINITION 2.15.** — An edge $e$ in $X_s$ is a rudimentary edge if it is of thickness one and moreover $X_s$ is a circle.

**LEMMA 2.16.** — A tubular graph of graphs is homotopically equivalent to a tubular graph of graphs with no rudimentary edges.

*Proof.* — Let $e$ be a rudimentary graph in a vertex graph $X_s$ of a tubular graph of graphs $X$. Since $X_s$ is a circle and attaching maps of edge graphs to $X_s$ are graph immersions, there exists exactly one edge $a$ incident to $s$ in the underlying graph $\Gamma_X$ and the attaching map from $X_a$ to $X_s$ is a graph isomorphism (see Figure 2.1).

Thus $X$ is homotopic to $X'$ obtained by removing $X_a$ and the open tube containing $X_a$. $\Gamma_{X'}$ is the graph obtained from $\Gamma_X$ by collapsing $a = (s, s')$ to $s'$. Repeating this procedure at each rudimentary edge gives the result. $\square$
## 2.4. Ends

The theory of ends of a topological space was first studied by Freudenthal [5]. The notion we require is that of “one-endedness”. We will use the following definition due to Specker (see [14] or [19]).

**DEFINITION 2.17.** — A locally finite CW complex $X$ is one-ended if for every compact set $K$, $X \setminus K$ has exactly one unbounded component.

It is a well-known fact that being one-ended is a quasi-isometry invariant (see [2, Proposition I.8.29], for instance). Then by an application of the Švarc–Milnor Lemma (see [2, Proposition I.8.19]), for instance), we have the following definition of one-endedness of a finitely presented group.

**PROPOSITION 2.18.** — Let $G$ be a finitely presented group and $X$ be a finite connected CW complex such that $G \cong \pi_1(X)$. $G$ is one-ended if and only if $\tilde{X}$ is one-ended.

## 3. Not one-ended

In this section, we will collect a few results that help determine when the fundamental group of a tubular graph of graphs is not one-ended.

**DEFINITION 3.1.** — Let $Z$ be a CW complex and $v \in Z$ be a vertex. Let $\tilde{v}$ denote a lift of $v$ in the universal cover $\tilde{Z}$ of $Z$. The star of $v$, denoted by $\text{star}(v)$, is the smallest subcomplex of $\tilde{Z}$ which contains all cells $\sigma$ such that $\tilde{v} \in \sigma$. The open star of $v$, denoted by $\text{star}^\circ(v)$, is the interior of $\text{star}(v)$.

We first recall a classical result due to Hopf:

**LEMMA 3.2 ([10]).** — Let $G$ be a torsion-free finitely generated group such that either

(1) $G = H * K$ is a nontrivial free splitting of $G$, or

(2) $G = H *_1 K$ is an HNN extension of a finitely generated group $H$ over its trivial subgroup.

Then $G$ is not one-ended.

We remark that the two conditions above are cases of an edge of groups with trivial edge group. We make a distinction between them because of the following standard lemma.
## 2.4. Ends

The theory of ends of a topological space was first studied by Freudenthal [5]. The notion we require is that of “one-endedness”. We will use the following definition due to Specker (see [14] or [19]).

**DEFINITION 2.17.** — A locally finite CW complex $X$ is one-ended if for every compact set $K$, $X \setminus K$ has exactly one unbounded component.

It is a well-known fact that being one-ended is a quasi-isometry invariant (see [2, Proposition I.8.29], for instance). Then by an application of the Švarc–Milnor Lemma (see [2, Proposition I.8.19]), for instance), we have the following definition of one-endedness of a finitely presented group.

**PROPOSITION 2.18.** — Let $G$ be a finitely presented group and $X$ be a finite connected CW complex such that $G \cong \pi_1(X)$. $G$ is one-ended if and only if $\tilde{X}$ is one-ended.

## 3. Not one-ended

In this section, we will collect a few results that help determine when the fundamental group of a tubular graph of graphs is not one-ended.

**DEFINITION 3.1.** — Let $Z$ be a CW complex and $v \in Z$ be a vertex. Let $\tilde{v}$ denote a lift of $v$ in the universal cover $\tilde{Z}$ of $Z$. The star of $v$, denoted by $\text{star}(v)$, is the smallest subcomplex of $\tilde{Z}$ which contains all cells $\sigma$ such that $\tilde{v} \in \sigma$. The open star of $v$, denoted by $\text{star}^\circ(v)$, is the interior of $\text{star}(v)$.

We first recall a classical result due to Hopf:

**LEMMA 3.2 ([10]).** — Let $G$ be a torsion-free finitely generated group such that either

(1) $G = H * K$ is a nontrivial free splitting of $G$, or

(2) $G = H *_1 K$ is an HNN extension of a finitely generated group $H$ over its trivial subgroup.

Then $G$ is not one-ended.

We remark that the two conditions above are cases of an edge of groups with trivial edge group. We make a distinction between them because of the following standard lemma.
<figure><img src="image_6.png" /><figcaption>Figure 3.1. Removing squares containing thickness-one edges.</figcaption></figure>

**LEMMA 3.3.** — Let $Z$ be a connected CW complex. Let $c \in Z$ be a vertex. Suppose that either

(1) $Z = Z_1 \vee_{\{c\}} Z_2$, with neither $Z_1$ nor $Z_2$ simply connected, or

(2) $\mathrm{star}(c) \setminus \{c\}$ is not connected, but $Z \setminus \{c\}$ is connected.

Then $\tilde{Z}$ is not one-ended.

**PROPOSITION 3.4.** — Let $X$ be a tubular graph of graphs with no hanging trees. Suppose there exists an edge of thickness zero. Then $\tilde{X}$ is not one-ended.

*Proof*. — Since all horizontal edges have thickness two, an edge of thickness zero has to be vertical. Let $e$ in $X_s$ be such an edge with midpoint $c$. Subdivide $e$ so that $c$ is a vertex of $X$. Either $X \setminus \{c\}$ is connected, or $X = X_1 \vee_c X_2$ is a wedge of two subcomplexes. Let $X_s = A \vee_c B$ be the induced decomposition of $X_s$. Since $e$ is not in a hanging tree, neither $A$ nor $B$ is a tree. Thus, $X_1$ and $X_2$ are not simply connected (as $\pi_1(A) \hookrightarrow \pi_1(X_1)$ and $\pi_1(B) \hookrightarrow \pi_1(X_2)$ in the graph of groups setup [18]). Lemma 3.3 then gives the result. $\square$

**PROPOSITION 3.5.** — Let $X$ be a tubular graph of graphs with no hanging trees and no rudimentary edges. Suppose there exists an edge of thickness one. Then $\tilde{X}$ is not one-ended.

*Proof*. — Let $e$ be an edge in $X_s \hookrightarrow X$ of thickness one and $s$ be the lone square containing $e$. We will show that $X$ is homotopic to a wedge of two non-simply connected square complexes.

Note that $X$ is homotopic to a complex obtained by removing the open square $s$ and the open edge $e$ (Figure 3.1). Removing $s$ decreases the thickness of a horizontal edge $f$ adjacent to $e$. We remove the only square that contains $f$, which in turn creates another horizontal edge of thickness one. We continue removing until we end up with a horizontal edge $f'$ (adjacent to $e$, see Figure 3.1) of thickness zero.
<figure><img src="image_7.png" /><figcaption>Figure 3.1. Removing squares containing thickness-one edges.</figcaption></figure>

LEMMA 3.3. — Let $Z$ be a connected CW complex. Let $c \in Z$ be a vertex.
Suppose that either

(1) $Z = Z_1 \vee_{\{c\}} Z_2$, with neither $Z_1$ nor $Z_2$ simply connected, or

(2) $\mathrm{star}(c) \setminus \{c\}$ is not connected, but $Z \setminus \{c\}$ is connected.

Then $\tilde{Z}$ is not one-ended.

PROPOSITION 3.4. — Let $X$ be a tubular graph of graphs with no hanging
trees. Suppose there exists an edge of thickness zero. Then $\tilde{X}$ is not one-
ended.

*Proof*. — Since all horizontal edges have thickness two, an edge of thickness zero has to be vertical. Let $e$ in $X_s$ be such an edge with midpoint $c$. Subdivide $e$ so that $c$ is a vertex of $X$. Either $X \setminus \{c\}$ is connected, or $X = X_1 \vee_c X_2$ is a wedge of two subcomplexes. Let $X_s = A \vee_c B$ be the induced decomposition of $X_s$. Since $e$ is not in a hanging tree, neither $A$ nor $B$ is a tree. Thus, $X_1$ and $X_2$ are not simply connected (as $\pi_1(A) \hookrightarrow \pi_1(X_1)$ and $\pi_1(B) \hookrightarrow \pi_1(X_2)$ in the graph of groups setup [18]). Lemma 3.3 then gives the result. $\square$

PROPOSITION 3.5. — Let $X$ be a tubular graph of graphs with no hanging
trees and no rudimentary edges. Suppose there exists an edge of thickness
one. Then $\tilde{X}$ is not one-ended.

*Proof*. — Let $e$ be an edge in $X_s \hookrightarrow X$ of thickness one and $s$ be the lone square containing $e$. We will show that $X$ is homotopic to a wedge of two non-simply connected square complexes.

Note that $X$ is homotopic to a complex obtained by removing the open
square $s$ and the open edge $e$ (Figure 3.1). Removing $s$ decreases the thick-
ness of a horizontal edge $f$ adjacent to $e$. We remove the only square that
contains $f$, which in turn creates another horizontal edge of thickness one.
We continue removing until we end up with a horizontal edge $f'$ (adjacent
to $e$, see Figure 3.1) of thickness zero.
Call the resulting subcomplex as $X'$. Either the midpoint of $f'$ does not disconnect $X'$, or $X'$ is a wedge of two subcomplexes $X_1$ and $X_2$, say (Figure 3.1). Note that $X_1$ is not simply connected as $X$ had neither hanging trees nor rudimentary edges. Also $X_2$ is not simply connected as $X_2$ is a subcomplex of $X$ which is not simply connected. By Lemma 3.3, $\tilde{X}$ is not one-ended. $\square$

**PROPOSITION 3.6.** — Suppose that every edge of $X$ has thickness at least two. If $\tilde{X}$ is one-ended, then the link of every vertex of $X$ is connected.

We will need the following result.

**LEMMA 3.7.** — Let $Z$ be a compact, connected nonpositively curved square complex which has at least one edge. If each edge of $Z$ is contained in at least two squares, then $\pi_1(Z)$ is infinite.

*Proof.* — Let $e$ be an edge of $Z$. The hyperplane $h_e$ dual to $e$ is a finite connected graph in which every vertex is of valence at least two, by the hypothesis on $Z$. This implies that $\pi_1(h_e)$ is a free group of positive rank. Any lift of $h_e$ embeds as a hyperplane in $\tilde{Z}$, since $\tilde{Z}$ is CAT(0) ([16, Theorem 4.10]). This implies that $\pi_1(h_e) \hookrightarrow \pi_1(Z)$. Hence the result. $\square$

*Proof of Proposition 3.6.* — Let $u \in X_s$ be a vertex whose link is not connected. This implies that $\text{star}(u) \setminus \{u\}$ is not connected. The result then follows from Lemma 3.3. Indeed, if $X = X_1 \vee_u X_2$, then $X_i$ is not simply connected by Lemma 3.7. $\square$

# 4. The second Brady–Meier criterion

In this section, we will assume that each edge of $X$ has thickness at least two and every vertex link is connected, but $X$ does not satisfy the second Brady–Meier criterion (BM2). We will explain how to simplify $X$ in this case by defining an opening of the complex at a vertex whose link does not satisfy (BM2). Fix one such vertex $u \in X_s \subset X$.

A vertex of link($u$) is *vertical* (*horizontal*) if it is a vertical (*horizontal*) half-edge incident to $u$ in $X$. Observe that the horizontal vertices have valence exactly two.

**LEMMA 4.1.** — *X does not satisfy (BM2) at u if and only if a vertical vertex of link(u) disconnects link(u).*

*Proof.* — One direction is clear. For the converse, there are two cases to consider: either a horizontal vertex $h$ or an edge $e$ of link($u$) disconnects link($u$).
Call the resulting subcomplex as $X'$. Either the midpoint of $f'$ does not disconnect $X'$, or $X'$ is a wedge of two subcomplexes $X_1$ and $X_2$, say (Figure 3.1). Note that $X_1$ is not simply connected as $X$ had neither hanging trees nor rudimentary edges. Also $X_2$ is not simply connected as $X_2$ is a subcomplex of $X$ which is not simply connected. By Lemma 3.3, $\tilde{X}$ is not one-ended. $\square$

**PROPOSITION 3.6.** — Suppose that every edge of $X$ has thickness at least two. If $\tilde{X}$ is one-ended, then the link of every vertex of $X$ is connected.

We will need the following result.

**LEMMA 3.7.** — Let $Z$ be a compact, connected nonpositively curved square complex which has at least one edge. If each edge of $Z$ is contained in at least two squares, then $\pi_1(Z)$ is infinite.

*Proof.* — Let $e$ be an edge of $Z$. The hyperplane $h_e$ dual to $e$ is a finite connected graph in which every vertex is of valence at least two, by the hypothesis on $Z$. This implies that $\pi_1(h_e)$ is a free group of positive rank. Any lift of $h_e$ embeds as a hyperplane in $\tilde{Z}$, since $\tilde{Z}$ is CAT(0) ([16, Theorem 4.10]). This implies that $\pi_1(h_e) \hookrightarrow \pi_1(Z)$. Hence the result. $\square$

*Proof of Proposition 3.6.* — Let $u \in X_s$ be a vertex whose link is not connected. This implies that $\text{star}(u) \setminus \{u\}$ is not connected. The result then follows from Lemma 3.3. Indeed, if $X = X_1 \vee_u X_2$, then $X_i$ is not simply connected by Lemma 3.7. $\square$

# 4. The second Brady–Meier criterion

In this section, we will assume that each edge of $X$ has thickness at least two and every vertex link is connected, but $X$ does not satisfy the second Brady–Meier criterion (BM2). We will explain how to simplify $X$ in this case by defining an opening of the complex at a vertex whose link does not satisfy (BM2). Fix one such vertex $u \in X_s \subset X$.

A vertex of link($u$) is *vertical* (horizontal) if it is a vertical (horizontal) half-edge incident to $u$ in $X$. Observe that the horizontal vertices have valence exactly two.

**LEMMA 4.1.** — *X does not satisfy (BM2) at u if and only if a vertical vertex of link(u) disconnects link(u).*

*Proof.* — One direction is clear. For the converse, there are two cases to consider: either a horizontal vertex $h$ or an edge $e$ of link($u$) disconnects link($u$).
<figure><img src="image_7.png" /><figcaption>Figure 4.1. link($u$)</figcaption></figure>

In the first case, let $v_1$ and $v_2$ be the two vertical vertices adjacent to $h$. Let $C$ be the component of link($u$) $\setminus \{h\}$ that contains $v_1$. Let $x \neq v_1 \in C$ be a vertex. Such a vertex exists as every edge of $X$ has thickness at least two. Then any path in link($u$) from $x$ to $v_2$ meets $h$, and hence meets $v_1$. Thus $v_1$ disconnects link($u$). In the second case, since horizontal vertices have valence two, it is easy to see that the unique vertical vertex incident on $e$ disconnects link($u$). $\square$

## The opening procedure

Throughout, we will denote an edge incident to $u$ and the corresponding vertex in link($u$) by the same notation. Let $e$ be a vertical edge incident to $u$ which disconnects link($u$). Let $C_1, \dots, C_n$ denote the maximal connected subgraphs of link($u$) $\setminus e$ (Figure 4.1), where maximality is by inclusion. We will denote by $f_{i1}, \dots, f_{ik_i}$ the vertical vertices in $C_i$ so that the vertical edges $f_{i1}, \dots, f_{ik_i}$ incident on $u$ belong to star($u, X_s$) (Figure 4.2). Let $x_{ij}$ denote the other endpoint of $f_{ij}$. We will now explain how to open star($u, X_s$):

**DEFINITION 4.2.** — The opening of star($u, X_s$) along $e$ is a tree $T_u$ (Figure 4.2) defined as follows: There is one “primary” vertex $v'$ out of which emit $n$ edges $e_1, \dots, e_n$, one for each $C_i$. For each $i$, we label the other endpoint of $e_i$ as $u_i$. From each $u_i$, we have $k_i$ edges to the vertices $x'_{i1}, \dots, x'_{ik_i}$ (compare with star($u, X_s$)). We label these edges as $f'_{i1}, \dots, f'_{ik_i}$. The opened-up graph of $X_s$ along $e$ is a graph $X'_s$ obtained by replacing $\star(u, X_s)$ in $X_s$ by $T_u$, with the obvious identifications.

Clearly, $X'_s$ is connected, $X_s \setminus \star(u, X_s) \hookrightarrow X'_s$ and $T_u \hookrightarrow X'_s$. There is a natural surjective map from $X'_s$ to $X_s$ which sends each $e_i$ in $T_u$ to $e$. Note that the graphs $X'_s$ and $X_s$ are homotopy equivalent.
<figure><img src="image_8.png" /><figcaption>Figure 4.1. link($u$)</figcaption></figure>

In the first case, let $v_1$ and $v_2$ be the two vertical vertices adjacent to $h$. Let $C$ be the component of link($u$) $\setminus \{h\}$ that contains $v_1$. Let $x \neq v_1 \in C$ be a vertex. Such a vertex exists as every edge of $X$ has thickness at least two. Then any path in link($u$) from $x$ to $v_2$ meets $h$, and hence meets $v_1$. Thus $v_1$ disconnects link($u$). In the second case, since horizontal vertices have valence two, it is easy to see that the unique vertical vertex incident on $e$ disconnects link($u$). $\square$

## The opening procedure

Throughout, we will denote an edge incident to $u$ and the corresponding vertex in link($u$) by the same notation. Let $e$ be a vertical edge incident to $u$ which disconnects link($u$). Let $C_1, \dots, C_n$ denote the maximal connected subgraphs of link($u$) $\setminus e$ (Figure 4.1), where maximality is by inclusion. We will denote by $f_{i1}, \dots, f_{ik_i}$ the vertical vertices in $C_i$ so that the vertical edges $f_{i1}, \dots, f_{ik_i}$ incident on $u$ belong to star($u, X_s$) (Figure 4.2). Let $x_{ij}$ denote the other endpoint of $f_{ij}$. We will now explain how to open star($u, X_s$):

**DEFINITION 4.2.** — The opening of star($u, X_s$) along $e$ is a tree $T_u$ (Figure 4.2) defined as follows: There is one “primary” vertex $v'$ out of which emit $n$ edges $e_1, \dots, e_n$, one for each $C_i$. For each $i$, we label the other endpoint of $e_i$ as $u_i$. From each $u_i$, we have $k_i$ edges to the vertices $x'_{i1}, \dots, x'_{ik_i}$ (compare with star($u, X_s$)). We label these edges as $f'_{i1}, \dots, f'_{ik_i}$. The opened-up graph of $X_s$ along $e$ is a graph $X'_s$ obtained by replacing $\star(u, X_s)$ in $X_s$ by $T_u$, with the obvious identifications.

Clearly, $X'_s$ is connected, $X_s \setminus \star(u, X_s) \hookrightarrow X'_s$ and $T_u \hookrightarrow X'_s$. There is a natural surjective map from $X'_s$ to $X_s$ which sends each $e_i$ in $T_u$ to $e$. Note that the graphs $X'_s$ and $X_s$ are homotopy equivalent.
<figure><img src="image_8.png" /><figcaption>Figure 4.2. Opening star($u$, $X_s$) to $T_u$</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>Figure 4.3. A highlighted path of each colour indicates a part of the image of an attaching map</figcaption></figure>

Construction

We now construct a new tubular graph of graphs $X'$ with the same underlying graph $\Gamma_X$ as $X$ and the only change is that $X'_s$ replaces $X_s$. An attaching map of an edge graph is unchanged if $u$ is not in the image, as $X_s \setminus \text{star}(u, X_s)$ embeds in $X'_s$. If $u$ is in the image, we do the obvious modification (see Figure 4.3 for an illustration).

*Notation.* — The tubular graph of graphs $X'$ is called an *SL-complex* (simplified link complex) of $X$, simplified link in the sense that the vertex $u$ has been replaced by $u_1, \dots, u_n$ where for each $i$, $\text{link}(u_i)$ is simpler than $\text{link}(u)$.

There exists a natural map from $X'$ to $X$. Further,
<figure><img src="image_9.png" /><figcaption>Figure 4.2. Opening star($u$, $X_s$) to $T_u$</figcaption></figure>

<figure><img src="image_10.png" /><figcaption>Figure 4.3. A highlighted path of each colour indicates a part of the image of an attaching map</figcaption></figure>

Construction

We now construct a new tubular graph of graphs $X'$ with the same underlying graph $\Gamma_X$ as $X$ and the only change is that $X'_s$ replaces $X_s$. An attaching map of an edge graph is unchanged if $u$ is not in the image, as $X_s \setminus \text{star}(u, X_s)$ embeds in $X'_s$. If $u$ is in the image, we do the obvious modification (see Figure 4.3 for an illustration).

*Notation.* — The tubular graph of graphs $X'$ is called an *SL-complex* (simplified link complex) of $X$, simplified link in the sense that the vertex $u$ has been replaced by $u_1, \dots, u_n$ where for each $i$, $\text{link}(u_i)$ is simpler than $\text{link}(u)$.

There exists a natural map from $X'$ to $X$. Further,
**PROPOSITION 4.3.** — *The tubular graphs of graphs X and $X'$ are homotopy equivalent.* ☐

Since the number of edges of $X_s'$ is strictly greater than the number of edges of $X_s$, we have

**LEMMA 4.4.** — *$X'$ is not isomorphic to $X$ as square complexes.* ☐

**LEMMA 4.5.** — *Every edge of $X'$ belongs to at least one square and the number of squares in $X'$ is the same as the number of squares in $X$.*

*Proof.* — The number of squares in $X'$ is equal to the total number of edges in the cyclic edge graphs, which is equal to the number of squares of $X$.

If a vertical edge does not belong to $T_u$, then since the attaching maps are unchanged from $X$, the vertical edge belongs to at least two squares. Similarly, each $f'_{ij}$ belongs to at least two squares. The edge $e_i$ belongs to a square if and only if a pair of adjacent edges $y_{\lambda_1}, y_{\lambda_2}$ in some edge graph is mapped to a pair $e, f_{ij}$. Such a pair exists as there is an edge between $e$ and $f_{ij}$ in link($u$). ☐

**Remark 4.6.** — It is possible that an edge $e_i$ incident to a $u_i$ in $T_u$ is of thickness one in $X'$. However, $e_i$ cannot be rudimentary as $X_s'$ is not a circle. In that case, by Proposition 3.5, $\tilde{X}$ is not one-ended.

# 5. The Algorithm

**DEFINITION 5.1.** — *A tubular graph of graphs is wedge-like if*

(1) it has no hanging trees or rudimentary edges, and

(2) either there exists a vertex whose link is not connected or there exists an edge of thickness one.

*Remark 5.2.* — By Proposition 3.4, Proposition 3.5 and Proposition 3.6, the fundamental group of a wedge-like tubular graph of graphs is not one-ended.

**THEOREM 5.3 (Main Theorem; Theorem A).** — *There is an explicit algorithm of polynomial time complexity that takes a tubular graph of graphs as input and returns a homotopy equivalent tubular graph of graphs which is either Brady–Meier, or is a point, or is wedge-like.*

*Proof.* — We will prove the theorem by constructing the algorithm. Let $X = X_0$ be the input tubular graph of graphs. Let $k \in \mathbb{N} \cup \{0\}$.
**PROPOSITION 4.3.** — *The tubular graphs of graphs X and X' are homotopy equivalent.* ☐

Since the number of edges of $X_s'$ is strictly greater than the number of edges of $X_s$, we have

**LEMMA 4.4.** — *X' is not isomorphic to X as square complexes.* ☐

**LEMMA 4.5.** — *Every edge of X' belongs to at least one square and the number of squares in X' is the same as the number of squares in X.*

*Proof.* — The number of squares in $X'$ is equal to the total number of edges in the cyclic edge graphs, which is equal to the number of squares of $X$.

If a vertical edge does not belong to $T_u$, then since the attaching maps are unchanged from $X$, the vertical edge belongs to at least two squares. Similarly, each $f_{ij}'$ belongs to at least two squares. The edge $e_i$ belongs to a square if and only if a pair of adjacent edges $y_{\lambda_1}, y_{\lambda_2}$ in some edge graph is mapped to a pair $e, f_{ij}$. Such a pair exists as there is an edge between $e$ and $f_{ij}$ in link($u$). ☐

**Remark 4.6.** — It is possible that an edge $e_i$ incident to a $u_i$ in $T_u$ is of thickness one in $X'$. However, $e_i$ cannot be rudimentary as $X_s'$ is not a circle. In that case, by Proposition 3.5, $\tilde{X}$ is not one-ended.

**5. The Algorithm**

**DEFINITION 5.1.** — *A tubular graph of graphs is wedge-like if*

(1) it has no hanging trees or rudimentary edges, and

(2) either there exists a vertex whose link is not connected or there exists an edge of thickness one.

*Remark 5.2.* — By Proposition 3.4, Proposition 3.5 and Proposition 3.6, the fundamental group of a wedge-like tubular graph of graphs is not one-ended.

**THEOREM 5.3 (Main Theorem; Theorem A).** — *There is an explicit algorithm of polynomial time complexity that takes a tubular graph of graphs as input and returns a homotopy equivalent tubular graph of graphs which is either Brady–Meier, or is a point, or is wedge-like.*

*Proof.* — We will prove the theorem by constructing the algorithm. Let $X = X_0$ be the input tubular graph of graphs. Let $k \in \mathbb{N} \cup \{0\}$.
Step 1 Check if $X_k$ has hanging subtrees. If yes, collapse each hanging subtree to a point and call the new complex also as $X_k$. Go to the next step.

Step 2 Check if $X_k$ has a rudimentary edge. If yes, remove tubes attached to rudimentary edges (Lemma 2.16) and call the resulting complex also as $X_k$. Go to the next step.

Step 3 Check if $X_k$ has at least one square. If yes, go to the next step. Otherwise, $X_k$ is either a point or wedge-like. Stop.

Step 4 Check if $X_k$ has an edge of thickness zero or one. If yes, $X_k$ is wedge-like. Stop. If not, go to the next step.

Step 5 Check if the link of every vertex of $X_k$ is connected. If yes, go to the next step. If not, $X_k$ is wedge-like. Stop.

Step 6 Check if $X_k$ satisfies (BM2). If yes, $X_k$ is Brady–Meier. Stop. If not, go to the next step.

Step 7 Replace $X_k$ by $X_{k+1} = X'_k$, an SL-complex of $X_k$, and go to Step 4.

We observe that for $l \ge k \ge 1$,

(i) $X_k \not\cong X_l$, as each opening increases the number of edges (Lemma 4.4).

(ii) $X_k$ and $X_l$ have the same number of squares (Lemma 4.5).

(iii) There is no edge of thickness zero in $X_k$ (Lemma 4.5).

(i) implies that the procedure above does not return a tubular graph of graphs from an earlier step. Since there are only a finite number of connected square complexes with a fixed number of squares (ii) and no thickness zero edges (iii), the procedure stops in finite time.

Checking if a graph has hanging trees takes linear time in the number of vertices and edges of $X$. Similarly, checking for edges of thickness zero or one or for rudimentary edges takes linear time in the number of edges and squares of $X$. Thus Steps 1 through 4 run in linear time in the number of vertices, edges and squares of $X$.

From Step 5 onwards, the number of vertices and edges of $X_k$ is bounded by the number of squares of $X_k$, as each edge is contained in a square. Steps 5 and 6 run in polynomial (quadratic) time in the number of squares: indeed, the size of a vertex link in $X_k$ is bounded by the number of squares of $X_k$ and checking for connectedness and disconnecting vertices in a vertex link is linear in the number of vertices and edges of the link (see [9] for details).

If $n$ is the number of squares in $X$, we claim that the number of times the algorithm goes back to Step 4 is at most $n$. Indeed, the algorithm performs the $k^{th}$ opening-up only if every square of $X_{k-1}$ is of thickness at least two. When each edge is of thickness at least two, the number of vertical edges (as well as horizontal edges) of a tubular graph of graphs can be at most
Step 1 Check if $X_k$ has hanging subtrees. If yes, collapse each hanging subtree to a point and call the new complex also as $X_k$. Go to the next step.

Step 2 Check if $X_k$ has a rudimentary edge. If yes, remove tubes attached to rudimentary edges (Lemma 2.16) and call the resulting complex also as $X_k$. Go to the next step.

Step 3 Check if $X_k$ has at least one square. If yes, go to the next step. Otherwise, $X_k$ is either a point or wedge-like. Stop.

Step 4 Check if $X_k$ has an edge of thickness zero or one. If yes, $X_k$ is wedge-like. Stop. If not, go to the next step.

Step 5 Check if the link of every vertex of $X_k$ is connected. If yes, go to the next step. If not, $X_k$ is wedge-like. Stop.

Step 6 Check if $X_k$ satisfies (BM2). If yes, $X_k$ is Brady–Meier. Stop. If not, go to the next step.

Step 7 Replace $X_k$ by $X_{k+1} = X'_k$, an SL-complex of $X_k$, and go to Step 4.

We observe that for $l \ge k \ge 1$,

(i) $X_k \not\cong X_l$, as each opening increases the number of edges (Lemma 4.4).

(ii) $X_k$ and $X_l$ have the same number of squares (Lemma 4.5).

(iii) There is no edge of thickness zero in $X_k$ (Lemma 4.5).

(i) implies that the procedure above does not return a tubular graph of graphs from an earlier step. Since there are only a finite number of connected square complexes with a fixed number of squares (ii) and no thickness zero edges (iii), the procedure stops in finite time.

Checking if a graph has hanging trees takes linear time in the number of vertices and edges of $X$. Similarly, checking for edges of thickness zero or one or for rudimentary edges takes linear time in the number of edges and squares of $X$. Thus Steps 1 through 4 run in linear time in the number of vertices, edges and squares of $X$.

From Step 5 onwards, the number of vertices and edges of $X_k$ is bounded by the number of squares of $X_k$, as each edge is contained in a square. Steps 5 and 6 run in polynomial (quadratic) time in the number of squares: indeed, the size of a vertex link in $X_k$ is bounded by the number of squares of $X_k$ and checking for connectedness and disconnecting vertices in a vertex link is linear in the number of vertices and edges of the link (see [9] for details).

If $n$ is the number of squares in $X$, we claim that the number of times the algorithm goes back to Step 4 is at most $n$. Indeed, the algorithm performs the $k^{th}$ opening-up only if every square of $X_{k-1}$ is of thickness at least two. When each edge is of thickness at least two, the number of vertical edges (as well as horizontal edges) of a tubular graph of graphs can be at most
equal to the number of squares. Observe that the opening procedure in Step 7 increases the number of vertical edges of $X_k$ by at least one, while decreasing the thickness of certain vertical edges. Thus, the algorithm continues at most until each vertical edge is contained in exactly two squares. □

As an immediate consequence, we have:

**COROLLARY 5.4 (Corollary 1.3).** — There is an algorithm of polynomial time complexity which takes as input a tubular graph of graphs and returns a homotopy equivalent tubular graph of graphs obtained by gluing together certain vertices of a finite collection of Brady–Meier tubular graphs of graphs and finite graphs. Further, the free product decomposition induced by cutting along the glued vertices is the Grushko decomposition of the fundamental group of the input tubular graph of graphs.

*Proof*. — Let $X$ be the input tubular graph of graphs with fundamental group $G$. Apply the algorithm of Theorem 5.3 to $X$. Let $X_N$ be the output. If $X_N$ is a point, then $G$ is trivial. If $X_N$ is Brady–Meier, $G$ has trivial Grushko decomposition. If $X_N$ is wedge-like, $G$ is a free product (Remark 5.2). We first remove every edge of thickness one in $X_N$ by the procedure of Figure 3.1.

Cut $X_N$ along an edge of thickness zero or a locally disconnecting vertex (in the obvious way). Either we get a connected tubular graph of graphs $X_1'$ or we get a disconnected space with components $X_1', \dots, X_n'$, where each $X_i'$ is a tubular graph of graphs. In the first case, $G = G_1 * \mathbb{Z}$. In the latter case, $G = G_1 * \dots * G_n$. Apply the algorithm again to each $X_i'$. If each $G_i$ is one-ended, we are done. Otherwise, cut again at an $X_i'$ with a many-ended $G_i$ and repeat. This procedure terminates in polynomial time. Indeed, at each step we get tubular graphs of graphs whose total number of squares is bounded by the number of squares of $X$. □

**Remark 5.5.** — We point out that we do not use Stallings’ theorem on ends for our proof. In fact, our procedure yields an alternate proof of Stallings’ theorem for fundamental groups of tubular graphs of graphs. Similarly, we do not assume the existence of the Grushko decomposition either. Our algorithm proves its existence for the groups under consideration.

By the uniqueness of the Grushko decomposition, we have:

**COROLLARY 5.6 (Corollary 1.4).** — Let $X$ be a tubular graph of graphs with fundamental group $G$. Suppose that $G$ admits a free splitting as $G = A * B$. Then there exist tubular graphs of graphs $X_1$ and $X_2$ such that $A$ and $B$ are fundamental groups of $X_1$ and $X_2$ respectively. Moreover, $X_1$ and $X_2$ can be so chosen such that the total number of squares in $X_1$ and $X_2$ is bounded by the number of squares in $X$. □
equal to the number of squares. Observe that the opening procedure in Step 7 increases the number of vertical edges of $X_k$ by at least one, while decreasing the thickness of certain vertical edges. Thus, the algorithm continues at most until each vertical edge is contained in exactly two squares. □

As an immediate consequence, we have:

**COROLLARY 5.4 (Corollary 1.3).** — There is an algorithm of polynomial time complexity which takes as input a tubular graph of graphs and returns a homotopy equivalent tubular graph of graphs obtained by gluing together certain vertices of a finite collection of Brady–Meier tubular graphs of graphs and finite graphs. Further, the free product decomposition induced by cutting along the glued vertices is the Grushko decomposition of the fundamental group of the input tubular graph of graphs.

*Proof*. — Let $X$ be the input tubular graph of graphs with fundamental group $G$. Apply the algorithm of Theorem 5.3 to $X$. Let $X_N$ be the output. If $X_N$ is a point, then $G$ is trivial. If $X_N$ is Brady–Meier, $G$ has trivial Grushko decomposition. If $X_N$ is wedge-like, $G$ is a free product (Remark 5.2). We first remove every edge of thickness one in $X_N$ by the procedure of Figure 3.1.

Cut $X_N$ along an edge of thickness zero or a locally disconnecting vertex (in the obvious way). Either we get a connected tubular graph of graphs $X_1'$ or we get a disconnected space with components $X_1', \dots, X_n'$, where each $X_i'$ is a tubular graph of graphs. In the first case, $G = G_1 * \mathbb{Z}$. In the latter case, $G = G_1 * \dots * G_n$. Apply the algorithm again to each $X_i'$. If each $G_i$ is one-ended, we are done. Otherwise, cut again at an $X_i'$ with a many-ended $G_i$ and repeat. This procedure terminates in polynomial time. Indeed, at each step we get tubular graphs of graphs whose total number of squares is bounded by the number of squares of $X$. □

**Remark 5.5.** — We point out that we do not use Stallings’ theorem on ends for our proof. In fact, our procedure yields an alternate proof of Stallings’ theorem for fundamental groups of tubular graphs of graphs. Similarly, we do not assume the existence of the Grushko decomposition either. Our algorithm proves its existence for the groups under consideration.

By the uniqueness of the Grushko decomposition, we have:

**COROLLARY 5.6 (Corollary 1.4).** — Let $X$ be a tubular graph of graphs with fundamental group $G$. Suppose that $G$ admits a free splitting as $G = A * B$. Then there exist tubular graphs of graphs $X_1$ and $X_2$ such that $A$ and $B$ are fundamental groups of $X_1$ and $X_2$ respectively. Moreover, $X_1$ and $X_2$ can be so chosen such that the total number of squares in $X_1$ and $X_2$ is bounded by the number of squares in $X$. □
**6. Whitehead graphs and separability**

The goal of this section is to give an alternative proof of Stallings’ algorithm to detect whether a finite set of words in a free group is separable (Corollary 6.2). We also give a new proof of Whitehead’s cut vertex theorem (Proposition 6.4).

Let $F_n$ be a free group of rank $n \ge 2$ and let $W$ be a finite set of non-trivial elements of $F_n$.

**DEFINITION 6.1 ([20]).** — *W is separable if there exists a non-trivial free splitting of $F_n = H * K$ such that each element of $W$ is either a conjugate of an element of $H$ or a conjugate of an element of $K$.*

In [20], Stallings developed an algorithm that detects whether $W$ is separable. We will use Theorem 5.3 to obtain an alternative algorithm:

**COROLLARY 6.2 (Stallings; Corollary 1.5).** — There exists an algorithm of polynomial time complexity that detects whether a given finite set of words in a finite rank free group is separable.

Our method is closely related to Stallings’, which uses Whitehead graphs [22] (defined below). Let $H_n$ denote the orientable 3 dimensional handlebody of genus $n$. Fix an identification of $F_n$ with the fundamental group of $H_n$. A basis $B$ of $F_n$ corresponds to a system of embedded disks $D = \{d_1, \dots, d_n\}$ such that for an element $b_i \in B$, $b_i$ is represented by a closed path in $H_n$ which starts from the chosen basepoint, intersects $d_i$ transversely and returns to the basepoint without touching any other $d_j$. Cutting open $H_n$ along these disks results in a 3-ball with $2n$ disks $d_i^\pm$ (such that the chosen representative $b_i$ enters along $d_i^+$ and leaves along $d_i^-$). $W$ is represented by a set of curves in $H_n$. After cutting, the set of curves is now a set of arcs between these discs.

**DEFINITION 6.3 ([22]).** — The Whitehead graph $\Gamma_{F_n, B}(W)$ is the graph with $2n$ vertices labelled $\{b_1^+, \dots, b_n^+\}$ and an edge between two vertices $b_i^+$ (respectively, $b_i^-$) and $b_j^+$ ($b_j^-$) for every arc coming from $W$ between the corresponding discs $d_i^+$ ($d_i^-$) and $d_j^+$ ($d_j^-$) in the cut up handlebody.

Figure 6.1 illustrates an example when $n = 2$, $B = \{b_1, b_2\}$ and $W = \{b_1b_2b_1\}$.

Recall that if $Y$ is a topological space, then a *cut point* $y \in Y$ is a point such that $Y \setminus \{y\}$ is not connected. There is a well-known result about the separability of $W$.
**6. Whitehead graphs and separability**

The goal of this section is to give an alternative proof of Stallings’ algorithm to detect whether a finite set of words in a free group is separable (Corollary 6.2). We also give a new proof of Whitehead’s cut vertex theorem (Proposition 6.4).

Let $F_n$ be a free group of rank $n \ge 2$ and let $W$ be a finite set of non-trivial elements of $F_n$.

**DEFINITION 6.1 ([20]).** — *W is separable if there exists a non-trivial free splitting of $F_n = H * K$ such that each element of $W$ is either a conjugate of an element of $H$ or a conjugate of an element of $K$.*

In [20], Stallings developed an algorithm that detects whether $W$ is separable. We will use Theorem 5.3 to obtain an alternative algorithm:

**COROLLARY 6.2 (Stallings; Corollary 1.5).** — There exists an algorithm of polynomial time complexity that detects whether a given finite set of words in a finite rank free group is separable.

Our method is closely related to Stallings’, which uses Whitehead graphs [22] (defined below). Let $H_n$ denote the orientable 3 dimensional handlebody of genus $n$. Fix an identification of $F_n$ with the fundamental group of $H_n$. A basis $B$ of $F_n$ corresponds to a system of embedded disks $D = \{d_1, \dots, d_n\}$ such that for an element $b_i \in B$, $b_i$ is represented by a closed path in $H_n$ which starts from the chosen basepoint, intersects $d_i$ transversely and returns to the basepoint without touching any other $d_j$. Cutting open $H_n$ along these disks results in a 3-ball with $2n$ disks $d_i^\pm$ (such that the chosen representative $b_i$ enters along $d_i^+$ and leaves along $d_i^-$). $W$ is represented by a set of curves in $H_n$. After cutting, the set of curves is now a set of arcs between these discs.

**DEFINITION 6.3 ([22]).** — The Whitehead graph $\Gamma_{F_n, B}(W)$ is the graph with $2n$ vertices labelled $\{b_1^+, \dots, b_n^+\}$ and an edge between two vertices $b_i^+$ (respectively, $b_i^-$) and $b_j^+$ ($b_j^-$) for every arc coming from $W$ between the corresponding discs $d_i^+$ ($d_i^-$) and $d_j^+$ ($d_j^-$) in the cut up handlebody.

Figure 6.1 illustrates an example when $n = 2$, $B = \{b_1, b_2\}$ and $W = \{b_1b_2b_1\}$.

Recall that if $Y$ is a topological space, then a *cut point* $y \in Y$ is a point such that $Y \setminus \{y\}$ is not connected. There is a well-known result about the separability of $W$.
<figure><img src="image_10.png" /><figcaption>Figure 6.1. A Whitehead graph</figcaption></figure>

**PROPOSITION 6.4 ([22]).** — If $W$ is separable, then for any basis $B$, the Whitehead graph $\Gamma_{F_n, B}(W)$ is either disconnected, or has a cut vertex.

More details can be found in [20]. We will re-prove Proposition 6.4 above using tubular graphs of graphs. Stallings constructs his algorithm to detect separability by choosing a Whitehead automorphism whenever there is a cut vertex in a Whitehead graph. Our strategy is to use the machinery of Theorem 5.3 when a Whitehead graph contains a cut vertex.

**6.1. Construction of a double**

Let $R_n$ denote an oriented rose with petals $\{a_1, \dots, a_n\}$. Fix an identification of $F_n$ with the fundamental group of $R_n$ such that each petal of $R_n$ in the positive direction represents a distinct element of the basis $B = \{b_1, \dots, b_n\}$. For each element $w_j \in W = \{w_1, \dots, w_k\}$, let $\phi_j : C_j \to R_n$ denote a cycle from the circle $C_j$ such that $\phi_j$ induces the word $w_j$ in $F_n$. We assume that $w_j$ is cyclically reduced so that $\phi_j$ is an immersion. Subdivide $R_n$ and each $C_j$ so that each $\phi_j$ is a simplicial immersion between simplicial graphs. Denote the subdivided $R_n$ by $X_s$.

We call the descendant $v$ in $X_s$ of the unique vertex of $R_n$ as the *special vertex* of $X_s$.

We define the *double* of $X_s$ along $W$ to be the tubular graph of graphs $X$ such that $X_s$ is a vertical graph of $X$ with exactly $k$ tubes attached to $X_s$ via the attaching maps $\phi_j$. Further, the underlying graph of $X$ consists of exactly two vertices and $k$ edges between them, where each vertex graph is isomorphic to $X_s$ and each edge graph is isomorphic to a unique $C_j$ with attaching map $\phi_j$ on both sides.
<figure><img src="image_11.png" /><figcaption>Figure 6.1. A Whitehead graph</figcaption></figure>

**PROPOSITION 6.4 ([22]).** — If $W$ is separable, then for any basis $B$, the Whitehead graph $\Gamma_{F_n, B}(W)$ is either disconnected, or has a cut vertex.

More details can be found in [20]. We will re-prove Proposition 6.4 above using tubular graphs of graphs. Stallings constructs his algorithm to detect separability by choosing a Whitehead automorphism whenever there is a cut vertex in a Whitehead graph. Our strategy is to use the machinery of Theorem 5.3 when a Whitehead graph contains a cut vertex.

**6.1. Construction of a double**

Let $R_n$ denote an oriented rose with petals $\{a_1, \dots, a_n\}$. Fix an identification of $F_n$ with the fundamental group of $R_n$ such that each petal of $R_n$ in the positive direction represents a distinct element of the basis $B = \{b_1, \dots, b_n\}$. For each element $w_j \in W = \{w_1, \dots, w_k\}$, let $\phi_j : C_j \to R_n$ denote a cycle from the circle $C_j$ such that $\phi_j$ induces the word $w_j$ in $F_n$. We assume that $w_j$ is cyclically reduced so that $\phi_j$ is an immersion. Subdivide $R_n$ and each $C_j$ so that each $\phi_j$ is a simplicial immersion between simplicial graphs. Denote the subdivided $R_n$ by $X_s$.

We call the descendant $v$ in $X_s$ of the unique vertex of $R_n$ as the *special vertex* of $X_s$.

We define the *double* of $X_s$ along $W$ to be the tubular graph of graphs $X$ such that $X_s$ is a vertical graph of $X$ with exactly $k$ tubes attached to $X_s$ via the attaching maps $\phi_j$. Further, the underlying graph of $X$ consists of exactly two vertices and $k$ edges between them, where each vertex graph is isomorphic to $X_s$ and each edge graph is isomorphic to a unique $C_j$ with attaching map $\phi_j$ on both sides.
LEMMA 6.5. — *The vertex link of every vertex of $X_s \subset X$ is connected with no cut vertices if and only if the link of the special vertex v is connected with no cut vertices.*

*Proof*. — The main case to consider is that of a vertex $u \neq v \in X_s$ whose vertex link is either not connected or has a cut vertex. Then there exists at most one path between the two vertical vertices $e_1, e_2$ in link($u$). There is a bijective correspondence between paths in link($u$) between $e_1$ and $e_2$ and paths in link($v$) between vertices that induce the petal in $R_n$ that contains $u$. Hence the result. □

The main lemma of this section is the following:

LEMMA 6.6. — *The link in $X$ of the special vertex $v$ is isomorphic as graphs to the first subdivision of the Whitehead graph $\Gamma_{F_n, B}(W)$.*

*Proof*. — Each petal of $R_n$ induces two vertical vertices in link($v$) and hence there are $2n$ vertical vertices. Paths of length two in link($v$) between these vertices correspond to the occurrence of the respective letters in a word $w_j$ of $W$. The isomorphism is then clear. □

*Proof of Proposition 6.4.* — Let $X$ be the double of $(X_s, W)$, with fundamental group $G$. $G$ is not one-ended as $W$ is separable. By Proposition 3.6, the link of some vertex of $X_s$ is either not connected or has a cut vertex. Lemma 6.5 and Lemma 6.6 then give the result. □

We will need the following result by Wilton [23, Theorem 18]:

THEOREM 6.7 (Wilton). — *The fundamental group of a graph of free groups with cyclic edge groups is freely indecomposable if and only if every vertex group is freely indecomposable relative to the incident edge groups.*

Note that a vertex group is freely indecomposable relative to the incident edge groups if and only if the set of words induced by the generators of these edge groups is not separable.

*Proof of Corollary 6.2.* — Let $W$ be the given set of words of the free group $F$. Let $X$ be the double of $(X_s, W)$ and $G$ its fundamental group. Apply the algorithm of Corollary 5.4 to detect whether $G$ is one-ended. By Theorem 6.7 above, $G$ is one-ended if and only if $W$ is not separable. □

## 7. The general case

We recall that by a *graph of groups* $\mathcal{G}$, we mean the following data: $\Gamma$ is a connected graph, called the underlying graph. For each vertex $s$ (edge $a$) of
LEMMA 6.5. — *The vertex link of every vertex of $X_s \subset X$ is connected with no cut vertices if and only if the link of the special vertex v is connected with no cut vertices.*

*Proof*. — The main case to consider is that of a vertex $u \neq v \in X_s$ whose vertex link is either not connected or has a cut vertex. Then there exists at most one path between the two vertical vertices $e_1, e_2$ in link($u$). There is a bijective correspondence between paths in link($u$) between $e_1$ and $e_2$ and paths in link($v$) between vertices that induce the petal in $R_n$ that contains $u$. Hence the result. □

The main lemma of this section is the following:

LEMMA 6.6. — *The link in $X$ of the special vertex $v$ is isomorphic as graphs to the first subdivision of the Whitehead graph $\Gamma_{F_n, B}(W)$.*

*Proof*. — Each petal of $R_n$ induces two vertical vertices in link($v$) and hence there are $2n$ vertical vertices. Paths of length two in link($v$) between these vertices correspond to the occurrence of the respective letters in a word $w_j$ of $W$. The isomorphism is then clear. □

*Proof of Proposition 6.4.* — Let $X$ be the double of $(X_s, W)$, with fundamental group $G$. $G$ is not one-ended as $W$ is separable. By Proposition 3.6, the link of some vertex of $X_s$ is either not connected or has a cut vertex. Lemma 6.5 and Lemma 6.6 then give the result. □

We will need the following result by Wilton [23, Theorem 18]:

THEOREM 6.7 (Wilton). — *The fundamental group of a graph of free groups with cyclic edge groups is freely indecomposable if and only if every vertex group is freely indecomposable relative to the incident edge groups.*

Note that a vertex group is freely indecomposable relative to the incident edge groups if and only if the set of words induced by the generators of these edge groups is not separable.

*Proof of Corollary 6.2.* — Let $W$ be the given set of words of the free group $F$. Let $X$ be the double of $(X_s, W)$ and $G$ its fundamental group. Apply the algorithm of Corollary 5.4 to detect whether $G$ is one-ended. By Theorem 6.7 above, $G$ is one-ended if and only if $W$ is not separable. □

## 7. The general case

We recall that by a *graph of groups* $\mathcal{G}$, we mean the following data: $\Gamma$ is a connected graph, called the underlying graph. For each vertex $s$ (edge $a$) of
Γ, $G_s$ ($G_a$) is a group. Further, whenever $a$ is incident to $s$, $\partial_{a,s}: G_a \to G_s$ is an injective homomorphism. Given a graph of groups as above, one can naturally associate with it a graph of spaces $\mathcal{X}_G$ with the same underlying graph Γ such that for each vertex $s$ (edge $a$) of Γ, $X_a$ ($X_s$) is a connected topological space such that $\pi_1(X_a) \cong G_a$ ($\pi_1(X_s) \cong G_s$). The fundamental group of the graph of groups $\mathcal{G}$ is the fundamental group of the geometric realisation of $\mathcal{X}_G$ (Section 2.2). We refer the reader to [17] for details. In this section, we freely switch between graphs of groups and graphs of spaces as required.

**THEOREM 7.1 (Theorem B).** — There is an algorithm of polynomial time complexity which takes a graph of free groups with cyclic edge groups as input and returns the Grushko decomposition of its fundamental group.

Before going into the proof, we recall the definitions of collapse and blow up. Given a graph of groups $\mathcal{G}$, and an edge $a$ of the underlying graph $\Gamma$ with endpoints $s_1, s_2$, by a *collapse* of the edge $s$ we mean a graph of groups $\mathcal{G}'$ with the following data: the underlying graph $\Gamma'$ is a quotient of $\Gamma$ with the edge $s$ collapsed to a point (vertex) $a_s$. The only change in vertex (edge) groups is the new vertex group $G_{a_s}$. $G_{a_s}$ is the fundamental group of the graph of groups whose underlying graph is the edge $s$, the vertex groups are $G_{s_1}$ and $G_{s_2}$ respectively and the edge group is $G_a$, with the injective homomorphisms from the edge group remaining the same as in $\mathcal{G}$.

An *elementary blow up* is the inverse operation of a collapse of an edge. A *blow up* is an iterated process of finitely many elementary blow up operations. Note that a collapse or blow up operation does not change the fundamental group.

We will also recall the notion of a relative Grushko decomposition. Let $F$ be a finite rank free group and let $W$ be a finite set of words in $F$. The relative Grushko decomposition of the pair $(F, W)$ is a free splitting of $F$ such that each element of $W$ conjugates into a free factor of the splitting. Further, each free factor of the splitting is itself freely indecomposable relative to $W$.

*Proof.* — Given a graph of free groups with cyclic edge groups $\mathcal{G}$, for each vertex $s$ of the underlying graph $\Gamma$, we have a pair $(G_s, W_s)$, where $G_s$ denotes the free vertex group at $s$ and $W_s$ is the set of words induced by generators of the incident edge groups. The Grushko decomposition of the fundamental group of $\mathcal{G}$ can be obtained in two steps:

(1) Obtain for each pair $(G_s, W_s)$ its *relative Grushko decomposition* $\mathcal{G}_s^{Gr}$ in the following way: For the pair $(G_s, W_s)$, let $X_s$ denote a suitable subdivision of an oriented rose with fundamental group $G_s$ (see Section 6.1) and let $Y_s$ denote its double. Apply Corollary 5.4
Γ, $G_s$ ($G_a$) is a group. Further, whenever $a$ is incident to $s$, $\partial_{a,s}: G_a \to G_s$ is an injective homomorphism. Given a graph of groups as above, one can naturally associate with it a graph of spaces $\mathcal{X}_G$ with the same underlying graph Γ such that for each vertex $s$ (edge $a$) of Γ, $X_a$ ($X_s$) is a connected topological space such that $\pi_1(X_a) \cong G_a$ ($\pi_1(X_s) \cong G_s$). The fundamental group of the graph of groups $\mathcal{G}$ is the fundamental group of the geometric realisation of $\mathcal{X}_G$ (Section 2.2). We refer the reader to [17] for details. In this section, we freely switch between graphs of groups and graphs of spaces as required.

**THEOREM 7.1 (Theorem B).** — There is an algorithm of polynomial time complexity which takes a graph of free groups with cyclic edge groups as input and returns the Grushko decomposition of its fundamental group.

Before going into the proof, we recall the definitions of collapse and blow up. Given a graph of groups $\mathcal{G}$, and an edge $a$ of the underlying graph $\Gamma$ with endpoints $s_1, s_2$, by a *collapse* of the edge $s$ we mean a graph of groups $\mathcal{G}'$ with the following data: the underlying graph $\Gamma'$ is a quotient of $\Gamma$ with the edge $s$ collapsed to a point (vertex) $a_s$. The only change in vertex (edge) groups is the new vertex group $G_{a_s}$. $G_{a_s}$ is the fundamental group of the graph of groups whose underlying graph is the edge $s$, the vertex groups are $G_{s_1}$ and $G_{s_2}$ respectively and the edge group is $G_a$, with the injective homomorphisms from the edge group remaining the same as in $\mathcal{G}$.

An *elementary blow up* is the inverse operation of a collapse of an edge. A *blow up* is an iterated process of finitely many elementary blow up operations. Note that a collapse or blow up operation does not change the fundamental group.

We will also recall the notion of a relative Grushko decomposition. Let $F$ be a finite rank free group and let $W$ be a finite set of words in $F$. The relative Grushko decomposition of the pair $(F, W)$ is a free splitting of $F$ such that each element of $W$ conjugates into a free factor of the splitting. Further, each free factor of the splitting is itself freely indecomposable relative to $W$.

*Proof.* — Given a graph of free groups with cyclic edge groups $\mathcal{G}$, for each vertex $s$ of the underlying graph $\Gamma$, we have a pair $(G_s, W_s)$, where $G_s$ denotes the free vertex group at $s$ and $W_s$ is the set of words induced by generators of the incident edge groups. The Grushko decomposition of the fundamental group of $\mathcal{G}$ can be obtained in two steps:

(1) Obtain for each pair $(G_s, W_s)$ its *relative Grushko decomposition* $\mathcal{G}_s^{Gr}$ in the following way: For the pair $(G_s, W_s)$, let $X_s$ denote a suitable subdivision of an oriented rose with fundamental group $G_s$ (see Section 6.1) and let $Y_s$ denote its double. Apply Corollary 5.4
to obtain a tubular graph of graphs $Y_s^{Gr}$ which induces the Grushko decomposition of $\pi_1(Y_s)$. Note that by Theorem 6.7, any free splitting of $\pi_1(Y_s)$ is a free splitting of $G_s$ relative to $W_s$. Thus the obtained Grushko decomposition of $\pi_1(Y_s)$ is a double over $W_s$ of the relative Grushko decomposition $G_s^{Gr}$ of $(G_s, W_s)$. Let $\Gamma_s$ denote the underlying graph of $G_s^{Gr}$.

(2) Modify $G$ by blowing-up each vertex $s$ to $G_s^{Gr}$. Let $G'$ be the new graph of groups. Note that the edge groups of $G'$ are either cyclic or trivial (trivial if and only if the edge belongs to some $\Gamma_s$). Collapse all edges with nontrivial edge group to obtain a new graph of groups $G^{Gr}$. By Theorem 6.7, the fundamental group of $G$ admits no other free splitting and hence $G^{Gr}$ is the required Grushko decomposition.

The running time of the above algorithm is of the order of the sum of the running times of the algorithms to obtain the relative Grushko decompositions in Step (1). But each such algorithm runs in polynomial time in the number of squares of $Y_s$. The number of squares of $Y_s$ is the sum of the lengths of the words of $W_s$ in $X_s$. Thus, the algorithm runs in polynomial time in the lengths of the words defined by the incident edge groups (in the respective vertex groups) of the input graph of free groups with cyclic edge groups. $\square$

Bibliography

[1] N. BRADY & J. MEIER, "Connectivity at infinity for right angled Artin groups", *Trans. Am. Math. Soc.* **353** (2001), no. 1, p. 117-132.

[2] M. R. BRIDSON & A. HAEFLIGER, *Metric spaces of non-positive curvature*, Grundlehren der Mathematischen Wissenschaften, vol. 319, Springer, 1999, xxii+643 pages.

[3] F. DAHMANI & D. GROVES, "Detecting free splittings in relatively hyperbolic groups", *Trans. Am. Math. Soc.* **360** (2008), no. 12, p. 6303-6318.

[4] G.-A. DIAO & M. FEIGHN, "The Grushko decomposition of a finite graph of finite rank free groups: an algorithm", *Geom. Topol.* **9** (2005), p. 1835-1880.

[5] H. FREudentHAL, "Über die Enden topologischer Räume und Gruppen", *Math. Z.* **33** (1931), no. 1, p. 692-713.

[6] V. GERASIMOV, "Detecting connectedness of the boundary of a hyperbolic group", unpublished, 1999.

[7] M. GROMOV, "Hyperbolic groups", in *Essays in group theory*, Mathematical Sciences Research Institute Publications, vol. 8, Springer, 1987, p. 75-263.

[8] I. GRUSCHKO, "Über die Basen eines freien Produktes von Gruppen", *Mat. Sb.*, N. Ser. **8** (1940), p. 169-182.

[9] J. HOPCROFT & R. TARJAN, "Algorithm 447: Efficient Algorithms for Graph Manipulation", *Commun. ACM* **16** (1973), no. 6, p. 372-378.

[10] H. HOPF, "Enden offener Räume und unendliche diskontinuierliche Gruppen", *Comment. Math. Helv.* **16** (1944), p. 81-100.
to obtain a tubular graph of graphs $Y_s^{Gr}$ which induces the Grushko decomposition of $\pi_1(Y_s)$. Note that by Theorem 6.7, any free splitting of $\pi_1(Y_s)$ is a free splitting of $G_s$ relative to $W_s$. Thus the obtained Grushko decomposition of $\pi_1(Y_s)$ is a double over $W_s$ of the relative Grushko decomposition $G_s^{Gr}$ of $(G_s, W_s)$. Let $\Gamma_s$ denote the underlying graph of $G_s^{Gr}$.

(2) Modify $\mathcal{G}$ by blowing-up each vertex $s$ to $G_s^{Gr}$. Let $\mathcal{G}'$ be the new graph of groups. Note that the edge groups of $\mathcal{G}'$ are either cyclic or trivial (trivial if and only if the edge belongs to some $\Gamma_s$). Collapse all edges with nontrivial edge group to obtain a new graph of groups $\mathcal{G}^{Gr}$. By Theorem 6.7, the fundamental group of $\mathcal{G}$ admits no other free splitting and hence $\mathcal{G}^{Gr}$ is the required Grushko decomposition.

The running time of the above algorithm is of the order of the sum of the running times of the algorithms to obtain the relative Grushko decompositions in Step (1). But each such algorithm runs in polynomial time in the number of squares of $Y_s$. The number of squares of $Y_s$ is the sum of the lengths of the words of $W_s$ in $X_s$. Thus, the algorithm runs in polynomial time in the lengths of the words defined by the incident edge groups (in the respective vertex groups) of the input graph of free groups with cyclic edge groups. $\square$

Bibliography

[1] N. BRADY & J. MEIER, "Connectivity at infinity for right angled Artin groups", *Trans. Am. Math. Soc.* **353** (2001), no. 1, p. 117-132.

[2] M. R. BRIDSON & A. HAEFLIGER, *Metric spaces of non-positive curvature*, Grundlehren der Mathematischen Wissenschaften, vol. 319, Springer, 1999, xxii+643 pages.

[3] F. DAHMANI & D. GROVES, "Detecting free splittings in relatively hyperbolic groups", *Trans. Am. Math. Soc.* **360** (2008), no. 12, p. 6303-6318.

[4] G.-A. DIAO & M. FEIGHN, "The Grushko decomposition of a finite graph of finite rank free groups: an algorithm", *Geom. Topol.* **9** (2005), p. 1835-1880.

[5] H. FREUDENTHAL, "Über die Enden topologischer Räume und Gruppen", *Math. Z.* **33** (1931), no. 1, p. 692-713.

[6] V. GERASIMOV, "Detecting connectedness of the boundary of a hyperbolic group", unpublished, 1999.

[7] M. GROMOV, "Hyperbolic groups", in *Essays in group theory*, Mathematical Sciences Research Institute Publications, vol. 8, Springer, 1987, p. 75-263.

[8] I. GRUSCHKO, "Über die Basen eines freien Produktes von Gruppen", *Mat. Sb.*, N. Ser. **8** (1940), p. 169-182.

[9] J. HOPCROFT & R. TARJAN, "Algorithm 447: Efficient Algorithms for Graph Manipulation", *Commun. ACM* **16** (1973), no. 6, p. 372-378.

[10] H. HOPF, "Enden offener Räume und unendliche diskontinuierliche Gruppen", *Comment. Math. Helv.* **16** (1944), p. 81-100.
[11] W. JACO, "Three-manifolds with fundamental group a free product", *Bull. Am. Math. Soc.* **75** (1969), p. 972-977.

[12] W. JACO, D. LETSCHER & J. H. RUBINSTEIN, "Algorithms for essential surfaces in 3-manifolds", in *Topology and geometry: commemorating SISTAG*, Contemporary Mathematics, vol. 314, American Mathematical Society, 2002, p. 107-124.

[13] S. K. M S, "Immersed cycles and the JSJ decomposition", *Algebr. Geom. Topol.* **20** (2020), no. 4, p. 1877-1938.

[14] F. RAYMOND, "The end point compactification of manifolds", *Pac. J. Math.* **10** (1960), p. 947-963.

[15] A. ROIG, E. VENTURA & P. WEIL, "On the complexity of the Whitehead minimization problem", *Int. J. Algebra Comput.* **17** (2007), no. 8, p. 1611-1634.

[16] M. SAGEEV, "Ends of group pairs and non-positively curved cube complexes", *Proc. Lond. Math. Soc.* **71** (1995), no. 3, p. 585-617.

[17] P. SCOTT & T. WALL, "Topological methods in group theory", in *Homological group theory (Proc. Sympos., Durham, 1977)*, London Mathematical Society Lecture Note Series, vol. 36, Cambridge University Press, 1979, p. 137-203.

[18] J.-P. SERRE, *Trees*, Springer, 1980, translated from the French by John Stillwell, ix+142 pages.

[19] E. SPECKER, "Die erste Cohomologiegruppe von Überlagerungen und Homotopie-Eigenschaften dreidimensionaler Mannigfaltigkeiten", *Comment. Math. Helv.* **23** (1949), p. 303-333.

[20] J. R. STALLINGS, "Whitehead graphs on handlebodies", in *Geometric group theory down under (Canberra, 1996)*, Walter de Gruyter, 1999, p. 317-330.

[21] N. W. M. TOUIKAN, "Detecting geometric splittings in finitely presented groups", *Trans. Am. Math. Soc.* **370** (2018), no. 8, p. 5635-5704.

[22] J. H. C. WHITEHEAD, "On equivalent sets of elements in a free group", *Ann. Math.* **37** (1936), no. 4, p. 782-800.

[23] H. WILTON, "One-ended subgroups of graphs of free groups with cyclic edge groups", *Geom. Topol.* **16** (2012), no. 2, p. 665-683.

[24] D. T. WISE, "Non-positively curved squared complexes: Aperiodic tilings and non-residually finite groups", PhD Thesis, Princeton University, 1996, 126 pages, https://www.proquest.com/docview/304259249.
[11] W. JACO, “Three-manifolds with fundamental group a free product”, *Bull. Am. Math. Soc.* **75** (1969), p. 972-977.

[12] W. JACO, D. LETSCHER & J. H. RUBINSTEIN, “Algorithms for essential surfaces in 3-manifolds”, in *Topology and geometry: commemorating SISTAG*, Contemporary Mathematics, vol. 314, American Mathematical Society, 2002, p. 107-124.

[13] S. K. M S, “Immersed cycles and the JSJ decomposition”, *Algebr. Geom. Topol.* **20** (2020), no. 4, p. 1877-1938.

[14] F. RAYMOND, “The end point compactification of manifolds”, *Pac. J. Math.* **10** (1960), p. 947-963.

[15] A. ROIG, E. VENTURA & P. WEIL, “On the complexity of the Whitehead minimization problem”, *Int. J. Algebra Comput.* **17** (2007), no. 8, p. 1611-1634.

[16] M. SAGEEV, “Ends of group pairs and non-positively curved cube complexes”, *Proc. Lond. Math. Soc.* **71** (1995), no. 3, p. 585-617.

[17] P. SCOTT & T. WALL, “Topological methods in group theory”, in *Homological group theory (Proc. Sympos., Durham, 1977)*, London Mathematical Society Lecture Note Series, vol. 36, Cambridge University Press, 1979, p. 137-203.

[18] J.-P. SERRE, *Trees*, Springer, 1980, translated from the French by John Stillwell, ix+142 pages.

[19] E. SPECKER, “Die erste Cohomologiegruppe von Überlagerungen und Homotopie-Eigenschaften dreidimensionaler Mannigfaltigkeiten”, *Comment. Math. Helv.* **23** (1949), p. 303-333.

[20] J. R. STALLINGS, “Whitehead graphs on handlebodies”, in *Geometric group theory down under (Canberra, 1996)*, Walter de Gruyter, 1999, p. 317-330.

[21] N. W. M. TOUIKAN, “Detecting geometric splittings in finitely presented groups”, *Trans. Am. Math. Soc.* **370** (2018), no. 8, p. 5635-5704.

[22] J. H. C. WHITEHEAD, “On equivalent sets of elements in a free group”, *Ann. Math.* **37** (1936), no. 4, p. 782-800.

[23] H. WILTON, “One-ended subgroups of graphs of free groups with cyclic edge groups”, *Geom. Topol.* **16** (2012), no. 2, p. 665-683.

[24] D. T. WISE, “Non-positively curved squared complexes: Aperiodic tilings and non-residually finite groups”, PhD Thesis, Princeton University, 1996, 126 pages, https://www.proquest.com/docview/304259249.