Kyungpook Mathematical Journal 2018; 58(2): 399-426
Cofinite Graphs and Groupoids and their Profinite Completions
Amrita Acharyya, Jon M. Corson and Bikash Das*
Department of Mathematics and Statistics, University of Toledo, Main Campus, Toledo, OH 43606-3390, USA, e-mail : Amrita.Acharyya@utoledo.edu, Department of Mathematics, University of Alabama, Tuscaloosa, AL 35487-0350, USA, email : jcorson@ua.edu, Department of Mathematics, University of North Georgia, Gainesville Campus, Oakwood, Ga. 30566, USA, email : Bikash.Das@ung.edu
*Corresponding Author.
Received: February 8, 2016; Accepted: April 1, 2018; Published online: June 23, 2018.

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

Cofinite graphs and cofinite groupoids are defined in a unified way extending the notion of cofinite group introduced by Hartley. These objects have in common an underlying structure of a directed graph endowed with a certain type of uniform structure, called a cofinite uniformity. Much of the theory of cofinite directed graphs turns out to be completely analogous to that of cofinite groups. For instance, the completion of a directed graph Γ with respect to a cofinite uniformity is a profinite directed graph and the cofinite structures on Γ determine and distinguish all the profinite directed graphs that contain Γ as a dense sub-directed graph. The completion of the underlying directed graph of a cofinite graph or cofinite groupoid is observed to often admit a natural structure of a profinite graph or profinite groupoid, respectively.

Keywords: profinite graph, cofinite graph, profinite group, cofinite group, profinite groupoid, cofinite groupoid, uniform space, completion, cofinite entourage
1. Introduction

Embedding an algebraic object, such as a group, ring, or module, into a projective limit of well-behaved objects is a frequently used tactic in algebra and number theory. For example, in commutative algebra, polynomial rings are embedded in rings of formal power series. Or more generally, if R is any commutative ring and I is an ideal, then the I-adic completion of R is the projective limit of the inverse system of quotient rings R/In, n ≥ 0. The case of R = ℤ and I = (p), where p is a prime, yields the p-adic integers. These rings are of particular importance in number theory.

This idea is also used for constructing compactifications of (discrete) graphs and directed graphs. For example, the ends of a finitely generated group are the ” boundary points ” of the so called end compactification of the Cayley (directed) graph of the group. The end compactification can be constructed as a certain completion of the (directed) graph which is a projective limit of finite (directed) graphs, and thus is a profinite (directed) graph (see Example 1.2). Similarly fundamental profinite groupoids are constructed using certain completions of fundamental groupoids (see 6.5).

There is a topological approach to producing such projective limits known as completion. The rough idea is to impose a suitable topology on the object making it into a topological group (or ring, or module, etc.) so that Cauchy sequences (or more generally, Cauchy nets) can be defined and used to construct the completion. By choosing different such topologies, various completions are formed. In the case of a residually finite group, Hartley [2] introduced the terminology of cofinite groups for the topological group structures that can be imposed such that the completion is a profinite group. Namely, a cofinite group is a topological group G whose open normal subgroups of finite indexeses form a neighborhood base for the identity. Our purpose in this paper is to investigate to what extent the technique of profinite completion can be extended to more general structures that may only have at most a partial multiplication; for instance, we consider graphs (in the sense of Serre [5]) and groupoids.

One feature that all the objects that will concern us here have in common is an underlying directed graph structure. (It may be quite simple, as in the case of a group, which we view as a directed graph whose vertex set consists of only the identity element.) Thus, we begin by exploring embeddings of directed graphs as dense sub-directed graphs of profinite directed graphs with the goal of developing a general theory that can be applied widely in many situations. Initially we note that, without some modification, the topological approach used in the classical situations to construct and distinguish various completions breaks down for directed graphs in general. The following easy example illustrates this point.

### Example 1.1

Let Γ be the directed graph obtained by subdividing the real line at the integer points, so V (Γ) = ℤ, and directing each edge in the increasing direction. Incidentally, Γ is the Cayley directed graph of the additive group ℤ with respect to the generating set {1}. We view Γ as a topological directed graph with the discrete topology. (Our terminology and notation for directed graphs is fully explained in the next section.)

For each integer n ≥ 0, let [−n, n] denote the connected sub-directed graph of Γ with vertex set {0,±1, . . . ,±n}. Thus [−n, n] is a combinatorial arc of length 2n. There is a unique retraction θn: Γ → [−n, n]; it is the simplicial map defined on vertices by θ(i) = i for −nin, θ(i) = n for in, and θ(i) = −n for i ≤ −n. Also form the quotient directed graph Γn = [−n, n]/(−n = n) obtained by identifying the vertex −n with the vertex n, and let qn : [−n, n] → Γn denote the natural quotient map. Thus Γn is a combinatorial circle of length 2n. Let φn = qnθn: Γ → Γn denote the composite map of directed graphs.

For integers 0 ≤ mn, let θmn: [−n, n] → [−m,m] be the restriction of the retraction θm: Γ → [−m,m], and note that θmnθn = θm. Also note that θmn determines a map of directed graphs φmn: Γn → Γm on the quotient directed graphs, and φmnφn = φm holds. We have constructed two inverse systems of finite directed graphs and maps of directed graphs indexed by the directed set of non-negative integers: ([−n, n], θmn) and (Γn, φmn). Denote their inverse limits by $Γ^1=lim← Γn$ and $Γ^2=lim←[-n,n]$. Endow each of the finite graphs [−n, n] and Γn with the discrete topology so that Γ̂1 and Γ̂2 are compact Hausdorff topological directed graphs.

Embed Γ in Γ̂1 via the canonical map of directed graphs determined by the compatible family of maps φn: Γ → Γn. Then it is easy to see that Γ̂1 = Γ∪ {∞} and its underlying topological space is the one-point compactification of the discrete underlying topological space of Γ. Similarly, Γ embeds in Γ̂2 as a dense discrete sub-directed graph and Γ̂2 = Γ∪ {−∞,∞} is a two-point compactification of Γ.

Thus Γ̂1 and Γ̂2 are non-isomorphic topological directed graphs, each containing Γ as a dense sub-directed topological directed graph. Thus endowing a directed graph Γ with a topological directed graph structure is not enough to uniquely determine a completion of Γ, and so something more is needed to define a suitable notion of a cofinite directed graph. Although, in the previous example, the relative topology that Γ inherits from each Γ̂i is the same, namely the discrete topology, the uniform structures they induce on Γ are different.

A profinite directed graph, like any compact Hausdorff space, has a unique uniformity that induces its topology. We explore this uniform structure on a profinite directed graph in Section 3, and characterize it in terms of what we call cofinite entourages (Theorem 3.4). Then by analyzing the relative uniform structure induced on a sub-directed graph of a profinite directed graph, a natural notion of cofinite directed graph is discovered (Definition 4.1). As justification for our definition, in Section 5 we show that every cofinite graph Γ has a unique completion Γ̄ (Theorem 5.6), and it is a profinite directed graph (Theorem 5.10). Moreover, profinite directed graphs are precisely the compact cofinite directed graphs.

In Section 6 we conclude that the paper has some applications that we are interested in for future reference. Specifically we consider graphs (in the sense of Serre [5]) and groupoids. These objects are directed graphs with an additional structure. We require that the cofinite directed graph structures on them also respect the additional structure. In the case of a graph, it turns out that in general the completion of a cofinite graph is a profinite graph. However for a cofinite groupoid, we need to impose a mild restriction to ensure that the completion is a groupoid. This condition automatically holds for groupoids with only finitely many identities (such as a group, which has a unique identity), and thus the completion of a cofinite groupoid with a finite vertex set is a profinite groupoid (Theorem 6.15).

We conclude the introduction by the following motivational example: The end compactification of a directed graph.

### Example 1.2

Let Γ be a connected, locally finite directed graph (see [6]). For each finite sub-directed graph ∑ of Γ, let R be the equivalence relation on Γ whose equivalence classes are the singleton subsets of E(∑) and the components of Γ E(∑). That is, (x, y) ∈ R if and only if x = y or x and y belong to the same component of Γ E(∑). Observe that R is compatible with the directed graph structure and has finite index (since Γ is connected). Let I be the non-empty directed set of all finite sub-directed graphs of Γ, partially ordered by inclusion. We have the following properties:

1. If ∑1,∑2I and ∑1 ⊆ ∑2, then R2 R1 .

2. For every x ∈ Γ, there exists ∑ ∈ I such that R(x) = {x}.

3. ∩∈I R = δΓ.

Hence the set {R | ∑ ∈ I} is a base for a (cofinite) uniformity on Γ. The completion of Γ (endowed with this cofinite structure) is given by $Γ^=lim← ΓΣ$ and is called the end compactification of Γ. In particular, the end compactification of Γ is a profinite directed graph and Γ is a discrete open sub-directed graph of Γ̂.

2. Preliminaries

### 2.1. Co-discrete Equivalence Relations

We do not distinguish between a binary relation and its graph. Thus, by a binary relation on a set X we mean simply a subset RX × X. Given a binary relation R on a set X and aX, we write R[a] = {xX | (a, x) ∈ R}. More generally, for any subset A of X, we put R[A] = ∪{R[a] | aA}.

The composition of two binary relations R and S on a set X, is the binary relation SRX ×X defined by: (x, z) ∈ SR if and only if there exists yX such that (x, y) ∈ R and (y, z) ∈ S. Note that composition is an associative operation on the set of binary relations on a set X.

The following lemma identifies certain equivalence relations on topological spaces that are useful in describing the uniform structure of profinite spaces. Recall that the index of an equivalence relation R on a set X is the cardinality of the set X/R of equivalence classes of X with respect to R.

Lemma 2.1

Let R be an equivalence relation on a topological space X. Then the following conditions are equivalent:

(1) The equivalence relation R is an open subset of the product space X × X.

(2) Every equivalence class R[a] is an open subset of X.

(3) The quotient space X/R is a discrete space.

Additionally when X is compact, such an equivalence relation R has finite index and is a clopen subset of X × X.

Proof

By the corollary to Proposition 4 of [1, Section I.4.2], (1) ⇒ (2). Being an equivalence relation,

$R=∪a∈X(R[a]×R[a])$

which makes it clear that (2) ⇒ (1). Note also that (2) ⇔ (3) since points are open in X/R if and only if equivalence classes are open in X. To show the last part, assume now that X is compact and that R is an equivalence relation on X satisfying the equivalent conditions (1)–(3). Then the quotient space X/R is compact and discrete, and thus a finite space. Consequently R is of finite indexes and it is closed in X × X since it is the finite union of the closed sets R[a] × R[a], for aX.

The inverse of R is the binary relation R−1 on X consisting of all pairs (y, x) ∈ X ×X such that (x, y) ∈ R. Note that the following properties hold for any binary relations R1, R2, and R3 on X:

1. (R1R2)R3 = R1(R2R3);

2. $(R1R2)-1=R2-1R1-1$;

3. if A is any subset of X, then (R1R2)[A] = R1(R2([A])).

### 2.2. Directed Graphs

A directed graph is a set Γ with a distinguished subset V (Γ) and two functions s, t: Γ → V (Γ) satisfying s(x) = t(x) = x for all xV (Γ). Each element of V (Γ) is called a vertex. We denote the complement of V (Γ) by E(Γ) = Γ V (Γ) and each eE(Γ) is called an edge with source s(e) and target t(e). Observe that the vertex set V (Γ) is determined by the source map s, and by the target map t: it is precisely the set of fixed points of each of these maps.

Sub-directed graphs

A subset ∑ of a directed graph Γ is called a sub-directed graph if it contains the source and target of each of its members. Under the restrictions of the source and target maps on Γ, a sub-directed graph ∑ is itself a directed graph. Note that V (∑) = V (Γ) ∩ ∑.

Products of directed graphs

Let (Γi)i∈I be a family of directed graphs. We make the Cartesian product Γ = Πi∈I Γi into a directed graph in the following way. The vertex set of Γ is the set V (Γ) = Πi∈I Vi) of the underlying sets. The source and target maps are defined coordinate-wise: if x = (xi) ∈ Γ, then s(x) = (s(xi)) and t(x) = (t(xi)). The set Γ with this directed graph structure is called a product directed graph.

Maps of directed graphs

A map of directed graphs is a function f : Γ → Δ between directed graphs that preserves sources and targets. Note that if f : Γ → Δ is a map of directed graphs, then f(V (Γ)) ⊆ V (Δ). For if xV (Γ), then f(x) = f(s(x)) = s(f(x)) and hence f(x) ∈ V (Δ). However f does not necessarily map edges to edges. Compositions of maps of directed graphs are maps of directed graphs. Also note that if f : Γ → Δ is a map of directed graphs and ∑ is a sub-directed graph of Γ, then f(∑) is a sub-directed graph of Δ.

Compatible equivalence relations on directed graphs

An equivalence relation R on the underlying set Γ is compatible equivalence relation on Γ if (s(x), s(y)) ∈ R and (t(x), t(y)) ∈ R whenever (x, y) ∈ R. In other words, an equivalence relation R on Γ is compatible with the directed graph structure if and only if R is a sub-directed graph of the product directed graph Γ × Γ.

If f : Γ → Δ is a map of directed graphs, then its kernel

$ker f={(x,y)∈Γ×Γ∣f(x)=f(y)}$

is clearly a compatible equivalence relation on Γ.

On the other hand, if R is any compatible equivalence relation on a directed graph Γ, then the set of equivalence classes Γ/R has a unique directed graph structure such that the natural map ν: Γ → Γ/R is a map of directed graphs. Its source and target maps are given by s(R[x]) = R[s(x)] and t(R[x]) = R[t(x)], and V (Γ/R) = ν(V (Γ)). Note that in this case kerν = R, and hence, every compatible equivalence relation on a directed graph Γ is the kernel of some map of directed graphs with domain Γ.

Moreover, we have this first isomorphism theorem for directed graphs: Let f : Γ → Δ be a map of directed graphs and let K = kerf. Then K is a compatible equivalence relation on Γ and there is an injective map of directed graphs f′: Γ/K → Δ given by K[x] ↦ f(x), which is an isomorphism when f is surjective.

The intersection of a non-empty family of compatible equivalence relations on a directed graph Γ is again a compatible equivalence relation on Γ. Thus, given any subset T ⊆ Γ × Γ, the intersection of all compatible equivalence relations on Γ containing T is the unique smallest such equivalence relation on Γ. It is denoted by T# and called the compatible equivalence relation on Γ generated by T. Alternatively, T# can be constructed as follows. Let 〈T〉 = T ∪ (s×s)[T] ∪ (t×t)[T], the smallest sub-directed graph of Γ × Γ containing T. Then T# = 〈T*, the reflexive and transitive closure of 〈T〉.

3. The Uniform Structure of a Profinite Directed Graph

A topological directed graph is a directed graph Γ endowed with a topology such that the source and target functions s, t: Γ → V (Γ) are continuous maps onto the subspace V (Γ). We form the category of topological directed graphs by taking the class of objects to consist of all topological directed graphs and taking the morphisms to be all continuous maps of directed graphs. (That is, a morphism is both continuous and a map of directed graphs.) It is clear that a morphism f : Γ → Δ is an isomorphism of topological directed graphs (i.e., an isomorphism in the category of topological directed graphs) if and only if f is both a bijective map of directed graphs and a homeomorphism.

Every sub-directed graph of a topological directed graph will be regarded as a topological directed graph with the subspace topology. Likewise, if K is a compatible equivalence relation on a topological directed graph Γ, then the quotient directed graph Γ/K will always be endowed with the quotient topology making it a topological directed graph. Also given any family of topological directed graphs (Γi)ı∈I, we make the product of the underlying topological spaces Γ = Πi∈I Γi into a topological directed graph with source and target maps given by s(xi) = (s(xi)) and t(xi) = (t(xi)). Then the projection maps φi: Γ → Γi are continuous maps of directed graphs and it is clear that Γ is the product in the category of topological graphs. Likewise the inverse limit of an inverse system of topological directed graphs and continuous maps of directed graphs exists in the category of topological directed graphs and its underlying topological space is the inverse limit of the corresponding inverse system of underlying spaces. (It can also be constructed as a sub-directed graph of a product of directed graphs in the usual way.)

A profinite directed graph is a compact, Hausdorff, totally disconnected directed graph. Equivalently, a profinite directed graph is a projective limit of finite discrete directed graphs; see, for instance, [4] or the remarks following the proof of Theorem 3.4. It is easy to see that any closed sub-directed graph of a profinite directed graph is a profinite directed graph and that products and inverse limits of profinite directed graphs are profinite directed graphs. Note that the vertex set V (Γ) of a profinite directed graph Γ is closed, since it is the fixed point set of a continuous map of a Hausdorff space to itself. On the other hand, the edge set E(Γ) = ΓV (Γ) need not be closed.

Recall that every compact Hausdorff space X has a unique uniformity that induces its topology. This uniformity consists of all neighborhoods of the diagonal δX in X × X; see, for instance, [1, II.4.1, Theorem 1]. Therefore, as we may, we regard every compact Hausdorff space as a uniform space endowed with the unique uniformity inducing its topology. Our goal in this section is to characterize profinite directed graphs in terms of their unique uniform structures.

For this purpose, we make use of the following observation.

### Lemma 3.1

Let X be a compact, Hausdorff, totally disconnected space and let W be an entourage of X. Then there exists an equivalence relation R on X such that R is open in X × X and RW. In particular, R has finite index and is an entourage of X.

Proof

Let I be the non-empty set of all equivalence relations R on X such that R is a clopen subset of X × X. Let x, yX with xy. Since X is Hausdorff and the clopen subsets of X form a base for its topology (see, for example, [7, Lemma 0.1.1(c)]), there is a clopen subset C of X with xC and y /∈ C. The equivalence relation R that partitions X into the two equivalence classes C and C′ = X C, namely

$R=(C×C)∪(C′×C′),$

is a clopen subset of X × X and (x, y) /∈ R. It follows that the intersection of the family I is equal to the diagonal δX in X × X.

By replacing W with its interior in X × X, we may assume that W is an open neighborhood of δX in X ×X. So for each RI, the set RW is closed in X ×X and

$∩R∈IRW⊆∩R∈IRδX=∅.$

However X ×X is compact, so there exist R1, . . . , RnI for some positive integer n such that (R1 W) ∩ · · · ∩ (Rn W) = ∅︀. Let R = R1 ∩ · · · ∩ Rn. Then R is an equivalence relation on X which is a clopen subset of X × X and RW. Furthermore, R is a neighborhood of δX in X ×X, and so R is an entourage of X.

To describe the uniform structure of profinite directed graphs and their sub-directed graphs, it is convenient to make the following definition.

### Definition 3.2.

(Cofinite entourage) Let Γ be a directed graph endowed with a uniformity. A cofinite entourage of Γ is a compatible equivalence relation of finite indexes on Γ which is also an entourage of Γ.

It should be noted that a directed graph Γ endowed with a uniformity always has at least one cofinite entourage, namely R = Γ × Γ. Here is a list of some fundamental properties of cofinite entourages that the reader can easily verify.

### Lemma 3.3

Let Γ and Δ be directed graphs endowed with uniformities. Then their cofinite entourages have the following properties.

(1) If R is a cofinite entourage of Γ and x ∈ Γ, then R[x] is a clopen neighborhood of x in Γ.

(2) Every cofinite entourage of Γ is a clopen subset of Γ × Γ.

(3) If R1and R2are cofinite entourages of Γ, then R1R2is also a cofinite entourage of Γ.

(4) If R is a compatible equivalence relation on Γ that contains a cofinite entourage of Γ, then R is itself a cofinite entourage.

(5) If f : Γ → Δ is a uniformly continuous map of directed graphs and S is a cofinite entourage of Δ, then (f × f)−1[S] is a cofinite entourage of Γ.

(6) Ifis a sub-directed graph of Γ and R is a cofinite entourage of Γ, then the restriction R ∩ (∑ × ∑) is a cofinite entourage on ∑.

We are now ready to give our characterization of profinite directed graphs in terms of their uniform structures.

### Theorem 3.4

Let Γ be a directed graph endowed with a compact Hausdorff topology. Then Γ is a profinite directed graph if and only if the set of cofinite entourages of Γ is a base for the uniformity on Γ.

Proof

Suppose first that Γ is a profinite directed graph and let W be an entourage of Γ. By Lemma 3.1, there exists an equivalence relation R on Γ such that R is open in X × X and RW. Let

$S=R∩(s×s)-1[R]∩(t×t)-1[R].$

Then S is an equivalence relation on Γ and it is open in X ×X. We claim that S is also a subgraph of Γ × Γ, and thus is a compatible equivalence relation on Γ. For if (x, y) ∈ S, then

(i) s(x, y) = (s(x), s(y)) ∈ R since (x, y) ∈ (s × s)1[R],

(ii) s(x, y) ∈ (s × s)1[R] since s(s(x), s(y)) = (s(x), s(y)) ∈ R, and

(iii) s(x, y) ∈ (t × t)1[R] since t(s(x), s(y)) = (s(x), s(y)) ∈ R.

Hence s(x, y) ∈ S. Similarly t(x, y) ∈ S, and therefore S is compatible. Furthermore, it is of finite indexes by Lemma 2.1. Hence S is a cofinite entourage of Γ such that SW. It follows that the set of all cofinite entourages of Γ is a base for the uniformity on Γ.

Conversely, assume now that the non-empty set, say I, of all cofinite entourages of Γ is a base for the uniformity on Γ. For each RI, the quotient ΓR = Γ/R is compact and discrete, and thus a (finite) profinite directed graph. Denote the quotient map Γ → ΓR by xxR. The map Γ → ΠR∈I ΓR given by x ↦ (xR) is a continuous map of directed graphs which is injective (as its kernel is ∩R∈I R = δΓ since I is a non-empty base for the uniformity on Γ and Γ is Hausdorff). Being an injective continuous map of a compact space to a Hausdorff space, this map is also a topological embedding. Thus Γ is isomorphic to a closed sub-directed graph of the profinite directed graph ΠR∈I ΓR and therefore is itself a profinite directed graph.

We observe now that Theorem 3.4 provides a canonical realization of a profinite directed graph Γ as a projective limit of finite directed graphs. Let I be the set of all cofinite entourages of Γ, partially ordered by reverse inclusion: R1R2 if and only if R1R2. Since the intersection of two cofinite entourages is a cofinite entourage, it follows that I is a directed set. For each RI, the quotient ΓR = Γ/R is compact and discrete, and thus a finite directed graph. Denote the natural quotient map by φR: Γ → ΓR. Note that for all RS in I, there exists a unique map of directed graphs φRS : ΓS → ΓR such that φRSφS = φR.

Moreover, (ΓR, φRS)R≤S∈I is an inverse system of finite discrete directed graphs. We claim that (Γ, φR)R∈I is its inverse limit. By the commutative diagrams above, (φR: Γ → Γ/R)R∈I is a compatible family of morphisms and so determines a morphism $φ:Γ→lim← ΓR$. Since each φR is surjective, the image φ(Γ) is a dense subset of $lim← ΓR$. But Γ is compact and $lim← ΓR$ is Hausdorff, and so φ(Γ) is closed. It follows that φ is surjective. Furthermore, I is a base for the uniformity on Γ (by Theorem 3.4) and Γ is Hausdorff, so

$ker φ=∩R∈Iker φR=∩R∈IR=δΓ.$

Therefore φ is also injective, and hence an isomorphism of topological directed graphs. This establishes our claim.

4. Cofinite Directed Graphs

Let Γ be a profinite directed graph and let ∑ be a sub-directed graph endowed with the induced uniformity. Then ∑ is Hausdorff and the family of all R∩(∑×∑) as R runs through all cofinite entourages of Γ, is a fundamental system of entourages of ∑. Since each R ∩ (∑ × ∑) is a cofinite entourage of the uniform sub-directed graph ∑, it follows that every uniform sub-directed graph ∑ of a profinite directed graph Γ has a fundamental system of entourages consisting of cofinite entourages of ∑. In light of this observation, we make the following definition.

### Definition 4.1

(Cofinite directed graph) A cofinite directed graph is a directed graph Δ endowed with a Hausdroff uniformity that has a base consisting of cofinite entourages of Δ.

Note that by virtue of Theorem 3.4, profinite directed graphs are precisely the compact cofinite directed graphs. Also note that the definition of cofinite directed graphs does not assume that the source and target maps are uniformly continuous, or even continuous. However, we next observe that this is automatically true.

### Theorem 4.2

Let Γ be a cofinite directed graph. Then the source and target maps s, t: Γ → V (Γ) are uniformly continuous maps onto the uniform subspace V (Γ). In particular, Γ is a Hausdorff topological graph and V (Γ) is a closed subset of Γ.

Proof

Let R be a cofinite entourage of Γ. Then

$(s×s)[R]⊆R∩[V(Γ)×V(Γ)] and (t×t)[R]⊆R∩[V(Γ)×V(Γ)]$

and thus s, t are uniformly continuous since the sets R ∩ [V (Γ) × V (Γ)], as R runs through all cofinite entourages of Γ, form a base for the relative uniformity on V (Γ). The last part follows since uniformly continuous maps are continuous and the vertex set of a Hausdorff topological directed graph is closed.

We always endow a cofinite directed graph with the topology induced by its uniformity, and as we just observed, this makes it into a Hausdorff topological directed graph. This topology can be characterized as follows.

Let Γ be a cofinite directed graph and let I be a non-empty set of cofinite entourages of Γ forming a base for the uniformity on Γ. We denote the closure of a subset A of Γ (in its uniform topology) by Ā, and note that it is given by

$A¯=∩R∈IR[A]$

and each R[A] is a clopen neighborhood of A in Γ; see, for instance, Proposition II. 1.2.2 and its corollary of [1]. Similarly, if W ⊆ Γ × Γ, then its closure in the product space Γ × Γ is given by

$W¯=∩R∈I(R×R)[W]=∩R∈IRWR$

and each RWR is a clopen neighborhood of W in Γ × Γ. See [1, Chapter II] or [3, Chapter 6] for more on the basic properties of uniform topologies.

As we noted above, every sub-directed graph of a profinite directed graph is a cofinite directed graph when it is endowed with its relative uniformity. On the other hand, cofinite directed graphs can be constructed from scratch as follows.

Let Γ be any abstract directed graph and let I be a filter base of compatible equivalence relations of finite indexes on Γ. (That is, I is a non-empty set with the property: if R1,R2I, then there exists R3I such that R3R1R2.)

Then I is a base for a uniformity on Γ; see for instance [3, Theorem 6.2]. Thus Γ endowed with this uniformity is a cofinite directed graph provided that the induced topology is Hausdorff. Moreover, it is obvious that all of the various cofinite structures that can be put on Γ arise in this way.

Amongst all uniform structures of this type that can be put on Γ, there is a unique maximal one, namely that in which I consists of all compatible equivalence relations of finite indexes on Γ. We next observe that Γ endowed with the finest uniformity is Hausdorff, and hence is a cofinite directed graph.

### Proposition 4.3

Let Γ be an abstract directed graph endowed with the unique finest uniformity having a base consisting of compatible equivalence relations of finite indexes on Γ. Then Γ is a discrete cofinite directed graph.

Proof

Let yV (Γ). Denote by Δ the finite (abstract) directed graph with V (Δ) = {a, b} and E(Δ) = {e, f, g, g}, where s(e) = t(e) = a, s(f) = t(f) = b, s(g) = a, t(g) = b, s(g) = b and t(g) = a. There is a unique map of directed graphs φ: Γ → Δ such that φ(y) = a and φ(x) = b for all vertices xy. The kernel R = kerφ is a compatible equivalence relation of finite indexes on Γ such that R[y] = {y}.

Now let yE(Γ) and let Δ = {a, e} be the finite directed graph with V (Δ) = {a}. Define a map of directed graphs φ: Γ → Δ by φ(y) = e and φ(x) = a for all xy. Then the kernel R = kerφ is a compatible equivalence relation of finite indexes on Γ such that R[y] = {y}.

We see that every singleton subset {y} of Γ is open in the topology induced by the uniformity on Γ, and hence this topology is discrete. In particular, Γ is Hausdorff, and so a cofinite directed graph.

It would be interesting to know which other filter bases I of compatible equivalence relations of finite indexeses on an abstract directed graph Γ, besides the largest one, make Γ into a cofinite directed graph. The following result helps with this.

### Proposition 4.4

If Γ is an abstract directed graph and I is a non-empty filter base of compatible equivalence relations of finite indexes on Γ, then the following conditions on Γ endowed with the uniformity generated by I are equivalent:

(1) Γ is Hausdorff, and so Γ is a cofinite directed graph;

(3) Γ is totally disconnected;

(2) ∩R∈I R = δΓ, the diagonal in Γ × Γ.

Proof

(1) ⇒ (2): Let x ∈ Γ and let C be the component of Γ containing x. For all RI, note that CR[x] since R[x] is a clopen set containing x. Furthermore, when Γ is Hausdorff, ∩R[x] = {x}, and thus C = {x} and Γ is totally disconnected.

(2) ⇒ (3): Let x, y ∈ Γ with xy. When Γ is totally disconnected, there exists an open set U of Γ with xU and y /∈ U since otherwise the subset {x, y} would be connected. Since U is open, there exists RI such that R[x] ⊆ U. Then y /∈ R[x] so that (x, y) /∈ R, and it follows that ∩R = δΓ.

(3) ⇒ (1): We have that δΓ = ∩ΓR = ∩R since δΓR and R2 = R as each RI is an equivalence relation. Thus, when (3) holds, δΓ is closed in Γ × Γ and thus Γ is Hausdorff.

Consequently, we see that every cofinite directed graph Γ is totally disconnected and that the intersection of all of its cofinite entourages is equal to the diagonal δΓ of Γ × Γ.

5. Completions of Cofinite Directed Graphs

In this section we define completions of cofinite directed graphs analogously to the way that completions of cofinite groups are defined in [2]. We show that every cofinite directed graph Γ has a completion Γ̄ (using a standard construction), and that it is unique up to a unique isomorphism extending the identity map on Γ. It turns out to be precisely the Hausdorff completion of its underlying uniform space (Corollary 5.7). Further generalizing the situation for cofinite groups [2], we observe that the completion Γ̄ is a profinite directed graph and that its cofinite entourages are precisely the closures in Γ̄ × Γ̄ of the cofinite entourages R of Γ. We begin with an analogue of [2, Theorem 2.1].

### Theorem 5.1

Let Γ be a cofinite directed graph which is embedded as a dense uniform sub-directed graph of a compact Hausdorff topological directed graph Γ̄. If Δ is any compact Hausdorff topological directed graph and f : Γ → Δ is a uniformly continuous map of directed graphs, then there exists a unique continuous map of directed graphs f̄ : Γ̄ → Δ extending f.

Proof

Being compact and Hausdorff, Δ is a complete uniform space. So there exists a unique uniformly continuous map : Γ̄ → Δ such that |Γ = f; see, for example, [1, II. 3.6, Theorem 2]. It remains to verify that is a map of directed graphs. Let B = {x ∈ Γ̄ | (s(x)) = s( (x))}. Then B is closed in Γ̄ since s and s are continuous maps from Γ to Δ and Δ is Hausdorff. However, Γ ⊆ B and Γ is dense in Γ̄. Thus B = Γ̄ and hence preserves sources. Similarly, preserves targets and thus is a map of directed graphs.

### Corollary 5.2

In the situation of the theorem, $f¯(Γ¯)=f(Γ)¯$.

Proof

Since is continuous, $f¯(Γ¯)⊆f¯(Γ)¯=f(Γ)¯$. On the other hand, f(Γ̄) ⊆ (Γ̄) and (Γ̄) is closed, since it is a compact subset of the Hausdorff space Δ. Thus $f(Γ)¯⊆f¯(Γ¯)$.

Based on the theorem above, we make the following definition.

### Definition 5.3

(Completion) Let Γ be a cofinite directed graph. Then any compact Hausdorff topological directed graph Γ̄ that contains Γ as a dense uniform sub-directed graph is called a completion of Γ.

As an immediate consequence of Theorem 5.1, we have the following result on uniqueness of completions.

### Corollary 5.4

If Γ̄1and Γ̄2are completions of a cofinite directed graph Γ, then there is an unique isomorphism of topological directed graphs ī: Γ̄1 → Γ̄2extending the identity map on Γ.

We turn now to the question of existence of completions. Let Γ be a cofinite directed graph and let I be any cofinal set of cofinite entourages of Γ. Note that (I,≤), where ≤ = ⊇ is the reverse of inclusion, is a directed set. Indeed ≤ is a partial order on I, and since I is cofinal, if R, SI, then there exists TI such that TRS, and so TR and TS.

For each RI, put ΓR = Γ/R (a finite discrete topological graph) and denote the quotient map Γ → ΓR by xxR. For R, SI with RS, observe that the identity map on Γ determines a map of directed graphs φRS: ΓS → ΓR given by φRS(xS) = xR; it is well defined since SR and continuous since ΓS is discrete. These maps have the properties:

(i) φRR = idΓ<sub>R sub>for all RI; and

(ii) φRSφST = φRT for all RST in I.

Hence we have an inverse system of (finite discrete) topological directed graphs and (surjective) continuous maps of directed graphs (ΓR, φRS)R≤S∈I, indexed by the directed set I.

Let $Γ^=lim← ΓR$ be the inverse limit of this inverse system (in the category of topological directed graphs) and denote the projection maps by φR : Γ̂ → ΓR. Then Γ̂ is a topological directed graph and there is a canonical map of directed graphs i: Γ → Γ̂ given by i(x) = (xR)R∈I. Moreover, Γ̂ is compact and Hausdorff since its underlying space is an inverse limit of compact Hausdorff spaces. Thus, as usual, we regard Γ̂ as a uniform space with the unique uniformity compatible with its topology. It should be noted that the pre-images under the projection maps φR : Γ̂ → ΓR of basis entourages of ΓR form a base for the uniformity on Γ̂ (see, for instance, [1]). However, being finite and discrete, {δΓ<sub>Rsub>} is a base for the uniformity on ΓR; and (φR × φR)1[δΓ<sub>Rsub>] = kerφR. Hence, the set of all ker φR, as R runs through I, is a base for the uniformity on Γ̂.

With this setup, we make the following observation.

### Lemma 5.5

If Γ is a cofinite directed graph, then $Γ^=lim← ΓR$ is a compact Hausdorff topological directed graph and the canonical map i: Γ → Γ̂ is a uniform embedding whose image i(Γ) is a dense sub-directed graph of Γ̂.

Proof

For each RI, note that (i × i)1[ker φR] = R and R is an entourage of Γ. Since the family of all ker φR, where R ranges over I, is a base for the uniformity on Γ̂, we see that i is uniformly continuous.

Since Γ is Hausdorff, ker i = ∩R∈I R = δΓ by Proposition 4.4. Thus i is injective. Further observe that (i × i)[R] = kerφR ∩ [i(Γ) × i(Γ)] for all RI (a base for the uniformity on Γ). Hence i is a uniform isomorphism from Γ onto the uniform subspace i(Γ) of Γ̂. That is, i is a uniform embedding.

Finally, note that for each RI, the image φR(i(Γ)) = ΓR. Therefore, since the underlying space of Γ̂ is the inverse limit of the underlying spaces of the ΓR, it follows that i(Γ) is dense in Γ̂.

Combining these observations we obtain the following result.

### Theorem 5.6

(Existence and uniqueness of completions) Every cofinite directed graph Γ has a completion, and it is unique up to an unique isomorphism of topological directed graphs extending the identity map on Γ.

### Corollary 5.7

If Γ is a cofinite directed graph, then its completion Γ is equal to the Hausdorff completion of the underlying uniform space of Γ.

Proof

Since a compact Hausdorff space (endowed with its unique compatible uniformity) is complete, this follows from [1, II. 3.6, Theorem 2].

In the definition of the completion of a cofinite directed graph Γ, we did not require that Γ̄ is a cofinite directed graph. However, it turns out that this is automatically true. In proving this and other things, we modify our notation as follows.

From now on, if A is a subset of a cofinite directed graph Γ, then Ā will denote the closure of A in the completion Γ̄. Thus the closure of Ā in Γ is given by ∩ Γ. Likewise, if W ⊂ Γ × Γ, then will denote the closure of W in the product space Γ̄ × Γ̄; and thus ∩ (Γ × Γ) is its closure in Γ × Γ. (That is, a bar over a set will mean its closure in the largest available space.) Note that this convention is consistent with denoting the completion of Γ by Γ̄ since Γ is dense in Γ̄. It is also consistent with denoting the unique extension given by Theorem 5.1 of a uniformly continuous map f from Γ to a compact Hausdorff topological directed graph Δ by : Γ̄ → Δ since is the closure in Γ̄ × Δ of the subset f ⊆ Γ × Δ.

We first prove a couple of lemmas.

### Lemma 5.8

If Γ is a cofinite directed graph and ∑̄ is a sub-directed graph of Γ, thenis a sub-directed graph of Γ and $V(Σ¯)=V(Σ)¯$. In particular, $V(Γ¯)=V(Γ)¯$.

Proof

Since s(∑) ⊆ ∑ and the source map is continuous, it follows that s(∑̄) ⊆ ∑̄. Similarly, t(∑̄) ⊆ ∑̄, and so ∑̄ is a subgraph of Γ̄. Its vertex set V (∑̄) = ∑̄ ∩ V (Γ̄) is a closed set containing V (∑), and thus $V(Σ)¯⊆V(Σ¯)$. On the other hand, $V(Σ¯)=s(Σ¯)⊆s(Σ)¯=V(Σ)¯$. Hence $V(Σ¯)=V(Σ)¯$.

It follows from this lemma that if Γ is a cofinite directed graph and ∑ is a sub-directed graph (endowed with the relative uniformity), then ∑̄ (endowed with the relative unifrormity) is the completion of ∑.

### Lemma 5.9

Let Γ be a cofinite directed graph and let Γ̄ be its completion. If R is a cofinite entourage of Γ, then its closure R̄ in Γ̄ × Γ̄ is a cofinite entourage of Γ̄ and R̄ ∩ (Γ × Γ) = R.

Proof

The natural map ν: Γ → Γ/R is a uniformly continuous map of directed graphs, and so by Theorem 5.1, it extends to a uniformly continuous map of directed graphs ν̄ : Γ̄ → Γ/R. Note that ker ν̄ is a cofinite entourage of Γ̄ since Γ/R is discrete. Also note that ker ν̄ ∩ (Γ × Γ) = ker ν = R. To complete the proof, it suffices to show that ker ν̄ = .

First note that R = ker ν ⊆ ker ν̄ and ker ν̄ is closed in Γ̄ × Γ̄. Thus R ⊆ ker ν̄. Conversely, let (x, y) ∈ ker ν̄ and let W be an open neighborhood of (x, y) in Γ̄×Γ̄. Then

$W∩R=W∩ker ν=W∩ker ν¯∩(Γ×Γ)≠∅$

since W ∩ ker ν̄ is a non empty open subset of Γ̄ × Γ̄ and Γ̄× Γ̄ is dense in Γ × Γ. So (x, y) ∈ , and thus the opposite inclusion ker ν̄ also holds.

### Theorem 5.10

Let Γ be a cofinite directed graph. Then its completion Γ̄ is a profinite directed graph and the cofinite entourages of Γ̄ are precisely all the R̄, where R runs through all cofinite entourages of Γ.

Proof

Let U be an entourage of Γ̄. Choose a closed entourage W such that WU; see, for example, [1, II. 1.2, Corollary 2]. Since W ∩ (Γ × Γ) is an entourage of Γ, there exists a cofinite entourage R of Γ such that RW ∩(Γ×Γ). By Lemma 5.9, is a cofinite entourage of Γ̄ and WU since W is closed. It follows that the cofinite entourages of Γ̄ form a fundamental system of entourages of Γ̄. Therefore Γ is a profinite directed graph by Theorem 3.4.

Now let S be any cofinite entourage of Γ̄ and put R = S ∩ (Γ × Γ). Then R is a cofinite entourage of Γ and it is dense in S, since S is a non-empty open subset of Γ̄ × Γ̄ and Γ× Γ is dense in Γ̄ × Γ̄. Thus, S = S = since S is also closed. Conversely, if R is a cofinite entourage of Γ, then is a cofinite entourage of Γ̄ by Lemma 5.9.

### Corollary 5.11

If Γ is a cofinite directed graph and R is a cofinite entourage of Γ, then the inclusion map Γ ↪ Γ̄ induces an isomorphism of topological directed graphs Γ/R → Γ̄/.

Proof

Let f : Γ → Γ̄/ be the map of directed graphs given by f(x) = [x], i.e., the map induced by the inclusion map Γ ↪ Γ̄. Note that f is onto since Γ is dense in Γ̄, and ker f = ∩(Γ×Γ) = R by Lemma 5.9. Thus, by the first isomorphism theorem for directed graphs, there is an isomorphism of directed graphs f′: Γ/R → Γ̄/ such that the following diagram commutes:

and f′ is also a homeomorphism since Γ/R and Γ̄/ are discrete.

### Example 5.12

Let Γ be a topological directed graph. Suppose that Γ is completely regular so that it is embedded in its Stone–Čech compactification β(Γ); we will regard Γ ⊆ β(Γ). We claim that β(Γ) has a unique topological directed graph structure such that Γ is a sub-directed graph. By the universal property of Stone–Čech compactifications, the source and target maps on Γ extend to continuous maps s, t : β(Γ) → β(Γ) and the extensions are unique. Note that s(s(x)) = s(x) and t(t(x)) = t(x) for all xβ(Γ) since these equations hold for all x in the dense subspace Γ. It is also easy to check that the fixed point sets of s and t in β(Γ) are both equal to $V(Γ)¯$ (the closure of V (Γ) in β(Γ)). Thus β(Γ) equipped with the unique continuous extensions of the source and target maps of Γ is a topological directed graph with $V(β(Γ))=V(Γ)¯$, and our claim follows.

### Theorem 5.13

Let Γ be a directed graph endowed with its maximal cofinite uniformity. Then β(Γ) is the completion of Γ.

Proof

By Proposition 4.3, Γ is discrete. So β(Γ) is a totally disconnected, compact Hausdorff space containing Γ as a subspace. (It is well known that the Stone–Čech compactification of a discrete space is totally disconnected.) Therefore, equipped with the unique topological directed graph structure such that Γ is a sub-directed graph (as constructed above), β(Γ) is a profinite directed graph.

Applying Theorem 3.4, we see that the set of all cofinite entourages of β(Γ) is a base for its uniformity and given any cofinite entourage S of β(Γ), note that S∩(Γ×Γ) is a cofinite entourage of Γ (since Γ has the maximal cofinite uniformity). Thus the inclusion map Γ ↪ β(Γ) is uniformly continuous.

On the other hand, suppose that R is any cofinite entourage of Γ (i.e., any compatible equivalence relation of finite indexes on Γ). Then Γ/R is a finite discrete directed graph (and thus a compact Hausdorff space), so the quotient map φR: Γ → Γ/R extends to a continuous map $φR′:β(Γ)→Γ/R$ which is a map of directed graphs (since the restriction to the dense sub-directed graph Γ is a map of directed graphs). Observe that $ker φR′$ is a cofinite entourage of β(Γ) and $ker φR′∩(Γ×Γ)=R$.

It follows that Γ is uniformly embedded in β(Γ), and hence β(Γ) is a compact Hausdorff topological directed graph that contains Γ as a dense uniform sub-directed graph. Consequently β(Γ) is the completion of Γ.

6. Applications

### 6.1. Cofinite Spaces

A cofinite space is a cofinite directed graph X with V (X) = X. In this case, the source and target maps are equal to the identity map on X, and so are irrelevant. The completion of a cofinite space X is also a cofinite space since $V(X¯)=V(X)¯=X¯$ (by Lemma 5.8), and it is compact. Thus is a profinite space (i.e., a compact Hausdorff totally disconnected space).

### 6.2. Cofinite Graphs

By a graph we mean a graph in the sense of Serre [5] and Stallings [6]. Thus a graph is a set Γ equipped with a source map s: Γ → Γ and an inversion map1: Γ → Γ such that for all x ∈ Γ,

$s(s(x))=s(x),(x-1)-1=x, and s(x)=x⇔x-1=x.$

The common fixed point set of these two maps is called the vertex set of Γ and is denoted by V (Γ) = {x ∈ Γ | s(x) = x} = {x ∈ Γ | x1 = x}. For x ∈ Γ, the vertex s(x) is called the source of x and we define the target of x to be the vertex t(x) = s(x1). We call x1 the inverse of x. The set E(Γ) = Γ V (Γ) is called the edge set of Γ. In other words, a graph is directed graph equipped with an involution that interchanges sources and targets and whose fixed point set is the vertex set.

A map of graphs is a function f : Γ → Δ between graphs that preserves sources and inverses. It then follows that targets are also preserved, and thus f is also a map of directed graphs.

Let R be an equivalence relation on a graph Γ. We say that R is a graph equivalence relation if Γ/R admits a structure of a graph such that the natural map ν: Γ → Γ/R is a map of graphs. In this case, it is clear that the graph structure on Γ/R is unique and given by: s(R[x]) = R[s(x)], t(R[x]) = R[t(x)], R[x]1 = R[x1], and V (Γ/R) = ν(V (Γ)). It is also easy to see that R is a graph equivalence relation if and only if these two conditions hold:

(1) if (x, y) ∈ R, then (s(x), s(y)) ∈ R and (x1, y1) ∈ R; and

(2) (x, s(x)) ∈ R if and only if (x, x1) ∈ R.

Definition 6.1

(Cofinite graph) Let Γ be a graph endowed with a uniformity. A cofinite graph entourage of Γ is a graph equivalence relation R of finite indexes on Γ which is also an entourage of Γ. We say that Γ is a cofinite graph if it is Hausdorff and its uniformity has a base consisting of cofinite graph entourages of Γ.

In particular, a cofinite graph Γ is a cofinite directed graph. So by Lemma 4.2, the source and target maps of a cofinite graph Γ are uniformly continuous, and by a similar argument, its involution is also uniformly continuous. Thus Γ is a Hausdorff topological graph (i.e., a graph endowed with a topology such that the source, target, and inversion maps are all continuous). Furthermore, by Theorem 5.10, its completion Γ̄ as a cofinite directed graph is a profinite directed graph. We show next that there is a unique involution on Γ̄ making it into a cofinite graph such that Γ is a subgraph (i.e., a sub-directed graph closed under the involution).

Theorem 6.2

If Γ is a cofinite graph, then its completion Γ̄ has a unique involution making it into a cofinite graph such that Γ is a subgraph. Moreover, the cofinite graph entourages of Γ̄ are precisely the closures R̄ in Γ̄ × Γ̄ of all cofinite graph entourages R of Γ.

Proof

Let Γ̄Reverse be the topological directed graph with the same underlying topological space as Γ̄ but with source and target maps interchanged. Then the map Γ → Γ̄Reverse given by xx1 is a map of directed graphs. Applying Theorem 5.1, we see that this map has a unique continuous extension to a map of directed graphs Γ → Γ̄Reverse. We denote this extension, regarded as a map from Γ̄ to itself (i.e., by composing with the identity map Γ̄Reverse → Γ̄), also by xx1. It is clearly the unique continuous extension to Γ̄ of the involution on Γ and satisfies the property: (x1)1 = x for all x ∈ Γ̄ (since this property holds on the dense subset Γ).

It remains to show that the fixed set A = {x ∈ Γ̄ | x = x1} of this involution is equal to V (Γ̄). Note first that A is a closed subset of Γ̄ containing V (Γ), and thus $V(Γ¯)=V(Γ)¯⊆A$ (using Lemma 5.8). To see the opposite inclusion, let xA and let R be a cofinite graph entourage of Γ. Then the natural map ν: Γ → Γ/R is a map of graphs, and in particular is involution-preserving. Since Γ is dense in Γ̄, it is clear that the unique continuous extension ν̄ : Γ̄ → Γ/R is also involution-preserving. Thus ν̄(x) = ν̄(x1) = ν̄(x)1. However Γ/R is a graph, and so ν̄(x) is a vertex of Γ/R. Since = kerν̄ (by the proof of Lemma 5.9) and the vertex set of Γ/R is ν(V (Γ)), it follows that x[V (Γ)]. However the set of closures of all cofinite graph entourages R of Γ form a base for the uniformity on Γ̄. Consequently $x∈V(Γ)¯$, and so xV (Γ̄) by Lemma 5.8.

To establish the second part, it suffices (by Theorem 5.10) to show that for each cofinite entourage R of Γ, is a graph equivalence relation on Γ̄ if and only if its closure R is a graph equivalence relation on Γ. However, this is an immediate consequence of Corollary 5.11 since it is clear that the induced isomorphism of directed graphs Γ/R → Γ̄/ is also involution-preserving. Thus ν: Γ → Γ/R is a map of graphs if and only if ν̄ : Γ̄ → Γ̄/ is a map of graphs.

### Corollary 6.3

If Γ is a cofinite graph, then its completion Γ̄ is a compact, Hausdorff, totally disconnected topological graph.

Proof

By Theorem 6.2, Γ̄ is a cofinite graph, and thus a topological graph. Moreover, it is compact, Hausdorff, and totally disconnected by Theorem 5.10.

### Remark

It is easy to see that a cofinite graph Γ is compact if and only if it is isomorphic to the inverse limit of an inverse system of finite discrete topological graphs and continuous maps of graphs. Such cofinite graphs are called profinite graphs. A somewhat more complicated fact is that profinite graphs are the same thing as compact, Hausdorff, totally disconnected topological graphs.

6.3. Cofinite Groupoids

Above we saw that the completions of cofinite spaces and cofinite graphs are profinite spaces and and profinite graphs, respectively. We will see that the situation for cofinite groupoids is more complicated in general.

To begin with, we review some basic groupoid theory. Recall that a groupoid is a small category in which every arrow is invertible. To be more precise, a groupoid is a directed graph G equipped with a partial binary operation (denoted by juxtaposition) satisfying these conditions: for all g, h, kG,

1. gh is defined if and only if t(g) = s(h), and in this case s(gh) = s(g) and t(gh) = t(h);

2. if t(g) = s(h) and t(h) = s(k), then (gh)k = g(hk);

3. s(g)g = g and gt(g) = g;

4. there exists g1G such that s(g1) = t(g), t(g1) = s(g) and gg1 = s(g), g1g = t(g).

Customarily the set of composable pairs in a groupoid G is denoted

$G(2)={(g,h)∈G×G∣t(g)=s(h)}.$

Then the partial binary operation on G is a function G(2)G, denoted by (g, h) ↦ gh. Likewise, we write G(3) for the set of composable triples in G. Then the associativity property (Axiom 2) can be stated as: if (g, h, k) ∈ G(3), then (gh)k = g(hk). Also note that there is an identity at each vertex v in a groupoid which we are taking to be v itself; by a standard argument, it is unique. Similarly, the inverse g1 of an element g satisfying Axiom 4 is unique.

A groupoid G with a single vertex is nothing other than a group, and in this case, V (G) = {1} and G(2) = G × G.

Given any groupoid G and vertices x, yV (G), we denote by G(x, y) the (possibly empty) set of all arrows from x to y in G. Note in particular that when x = y, the set G(x, x) is a subgroupoid of G with a single vertex, and hence is a group. The groups G(x, x), for xV (G), are called the vertex groups or local groups of G.

If G and H are groupoids, a homomorphism φ: GH is a function with the property: if (g1, g2) ∈ G(2), then (φ(g1), φ(g2)) ∈ H(2) and φ(g1g2) = φ(g1)φ(g2). In this situation, it is easy to check that φ is also a map of directed graphs.

A subset H of a groupoid G is a subgroupoid of G if:

(1) H is a sub-directed graph of G;

(2) if h1, h2H and (h1, h2) ∈ G(2), then h1h2H; and

(3) h1H whenever hH.

In this case, H is itself a groupoid under the restrictions of the operations on G.

The product groupoid of groupoids G1 and G2 is the directed graph G1 × G2 with partial binary operation (G1 × G2)(2)G1 × G2 defined as follows. If (g1, g2), (h1, h2) ∈ G1 × G2 and t(g1, g2) = s(h1, h2), then (g1, g2)(h1, h2) = (g1h1, g2h2). The product of an arbitrary family of groupoids is defined similarly.

An equivalence relation ρ on a groupoid G is called a congruence if it is also a subgroupoid of the product groupoid G × G. That is, a congruence on G is an equivalence relation ρ on G with the properties:

(1) if (g, h) ∈ ρ, then (s(g), s(h)) ∈ ρ and (t(g), t(h)) ∈ ρ;

(2) if (g1, g2), (h1, h2) ∈ ρ and t(g1, g2) = s(h1, h2), then (g1h1, g2h2) ∈ ρ; and

(3) if (g, h) ∈ ρ, then (g1, h1) ∈ ρ.

However, in this situation, the quotient of the underlying directed graph G/ρ need not admit a structure of a groupoid such that the natural map ν : GG/ρ is a homomorphism. For instance, suppose G has distinct vertices x, y, z,w such that G(x, y) and G(z,w) are non-empty but G(x,w) = ∅︀. Let ρ be the congruence on G that identifies y to z. Then G/ρ has arrows from ν(x) to ν(y) = ν(z) and arrows from ν(y) = ν(z) to ν(w), but no arrows from ν(x) to ν(w). Hence G/ρ does not admit any structure of a groupoid at all.

To avoid this difficulty, we restrict our attention to a certain type of congruences that behave better. To describe these, we make use of the following notation. If Γ is any directed graph (for example, a groupoid) and n is a positive integer, let Γ(n) denote the set of consecutive n-tuples (x1, . . . , xn) of elements of Γ (i.e., t(xi) = s(xi+1) for all 1 ≤ in – 1). Given any map of directed graphs f : Γ → Δ, we use the same symbol to denote the induced map on the sets of consecutive n-tuples f : Γ(n) → Δ(n) given by f(x1, . . . , xn) = (f(x1), . . . , f(xn)). Let denote the category whose class of objects consists of all directed graphs and whose morphisms are all maps of directed graphs f : Γ → Δ such that f(3)) = Δ(3). We call these morphisms -maps. Note that if f : Γ → Δ is a -map, then f is surjective and also f(2)) = Δ(2). Finally, we say that a homomorphism of groupoids f : GH is a -homomorphism if its underlying map of directed graphs is a -map.

By a -congruence on a groupoid G, we mean a congruence ρ on G whose natural homomorphism ν : GG/ρ is a -map. In this situation, the quotient G/ρ of the underlying directed graph of G admits a unique groupoid structure such that ν is a -homomorphism. The inversion map and partial product on G/ρ are given by ν(g)1 = ν(g1) and ν(g1)ν(g2) = ν(g1g2) for all gG and (g1, g2) ∈ G(2), which are well-defined since ρ is a congruence and ν(G(2)) = (G/ρ)(2). Associativity of this partial product on G/ρ carries over from G since ν(G(3)) = (G/ρ)(3).

### Definition 6.4

Let G be a groupoid endowed with a uniformity. A cofinite congruence on G is a -congruence ρ of finite indexes on G such that ρ is also an entourage of G. We say that G is a cofinite groupoid if it is Hausdorff and the set of cofinite congruences on G is a base for its uniformity.

Note that a cofinite groupoid has an underlying cofinite directed graph structure, and thus has uniformly continuous source and target maps by Lemma 4.2. We observe next that the same goes for the involution and partial product maps.

### Lemma 6.5

Let G be a cofinite groupoid. Then the involution map GG, gg1, and the partial product G(2)G, (g, h) ↦ gh, are uniformly continuous maps.

Proof

Since the cofinite congruences ρ on G form a base for its uniformity, and (g1, h1) ∈ ρ whenever (g, h) ∈ ρ, it follows that the involution map gg1 is uniformly continuous. Also given any cofinite congruence ρ on G, (ρ × ρ) ∩ G(2) is an entourage of G(2) such that: for all (g1, h1), (g2, h2) ∈ G(2), if (g1, g2) ∈ ρ and (h1, h2) ∈ ρ, then (g1h1, g2h2) ∈ ρ. Thus the partial product G(2)G is a uniformly continuous map.

In particular, it follows from Lemma 6.5 that a cofinite groupoid is a Hausdorff topological groupoid. Recall that a topological groupoid is a groupoid G endowed with a topology such that the maps GG, gg1 and G(2)G, (g, h) ↦ gh, are continuous (where G(2) is endowed with the subspace topology of the product space G × G). Note that in this situation, the source and target maps are also continuous since s(g) = gg1 and t(g) = g1g. Hence a topological groupoid has an underlying topological directed graph structure. The category of topological groupoids is the category whose objects are topological groupoids and whose morphisms are continuous homomorphisms of groupoids.

Every subgroupoid H of a topological groupoid G is given the subspace topology and thus becomes a topological groupoid. The product of a family (Gi)i∈I of topological groupoids exists in the category of topological groupoids and can be constructed by taking the product ΠGi of the underlying topological spaces and giving it the groupoid structure described above. Similarly, the inverse limit of an inverse system of topological groupoids and continuous homomorphisms exists in the category of topological groupoids, and its underlying topological space is the inverse limit of the corresponding inverse system of underlying spaces.

It is clear that each vertex group of a topological groupoid is a topological group. For cofinite groupoids we can say even more.

### Proposition 6.6

If G is a cofinite groupoid and xV (G), then the vertex group G(x, x) is a cofinite group.

Proof

Since G is Hausdorff, G(x, x) is also Hausdorff.

The set {ρ[x] ∩ G(x, x) | ρ is a cofinite congruence on G} is a base of open neighborhoods for the identity x in G(x, x). However, if ρ is a cofinite congruence on G, then ρ ∩ [G(x, x) × G(x, x)] is a congruence of finite indexes on the group G(x, x) and ρ[x] ∩ G(x, x) is the congruence class of the identity. It follows that each ρ[x] ∩ G(x, x) is a normal subgroup of finite indexes in G(x, x). Hence the identity in G(x, x) has a neighborhood base consisting of open normal subgroups of finite indexes in G(x, x), and hence is a cofinite group.

Note that every cofinite groupoid G has an underlying cofinite directed graph structure. We let denote the completion of the underlying cofinite directed graph of G. We make use of the following lemma below.

### Lemma 6.7

Let G be any cofinite groupoid. Then G(2)is dense in Ḡ(2)(as subspaces of the product space Ḡ × Ḡ).

Proof

Let ρ be a cofinite congruence on Γ and let ν : GG/ρ be the natural map. Let ν̄ : G/ρ be the unique continuous extension of ν. Since ρ is a -congruence, ν̄(G(2) = (G/ρ)(2) and thus ν̄[G(2)] = (Ḡ/ρ̄)(2) also holds (by Corollary 5.11). Since ρ̄ = kerν̄ (by the proof of Lemma 5.9), it follows that (2) ⊆ (ρ̄ × ρ̄)[G(2)] = ∪(g,h)∈G(2) (ρ̄[g] × ρ̄[h]). Let I be the non-empty set of all cofinite congruence on Γ. Then using Theorem 5.10, we see that the set {ρ̄ × ρ̄ | ρI} is a base for the product uniformity on × . Thus $G¯(2)⊆∩ρ∈I(ρ¯×ρ¯)[G(2)]=G(2)¯$. It follows that G(2) is dense in (2)

### Theorem 6.8

Let G is a cofinite groupoid. Then Ḡ admits a unique topological groupoid structure such that G is a uniform subgroupoid. Moreover, equipped with this structure, Ḡ is a profinite groupoid.

Proof

Construct using the standard construction of Lemma 5.5 with I equal to the set of all cofinite congruences ρ on G. Since I is a base for the uniformity on G, it is a cofinal set of cofinite entourages of the underlying cofinite graph of G. Thus $G¯=lim←ρ∈IG/ρ$ is the completion of the underlying cofinite directed graph of G. For each ρI, equip G/ρ with its unique groupoid structure such that the natural map GG/ρ is a homomorphism. Then each G/ρ is a discrete toplological groupoid. Moreover, by the definition of the operations on G/ρ, it is clear that if ρ, σI with ρσ, then φρσ : G/σG/ρ is a homomorphism of groupoids. Now is a profinite groupoid and the canonical map G is a uniform embedding and a homomorphism. Uniqueness of this topological groupoid structure on follows from G being dense in and G(2) being dense in (2) (by Lemma 6.7).

The following corollaries of Theorem 6.8 are worth noting. The first is an immediate consequence.

### Corollary 6.9

If G is a compact cofinite groupoid, then G is a profinite groupoid.

### Corollary 6.10

Let G be a cofinite groupoid and equip Ḡ with its unique topological groupoid structure such that G is a uniform subgroupoid. If ρ is any cofinite congruence on G, then ρ̄ is a cofinite congruence on Ḡ. Moreover, all cofinite congruences on Ḡ are of this form.

Proof

By the proof of Theorem 5.9, ρ̄ = kerν̄, where ν̄ : G/ρ is the unique continuous extension of the natural map ν : GG/ρ. Endow G/ρ with the unique groupoid structure such that ν is a homomorphism. Then applying Lemma 6.7, we see that ν̄ is also a homomorphism. Therefore ρ̄ = kerν̄ is a congruence on . Let η : Ḡ/ρ̄ be the natural map. Since ν is a -map, it follows from Corollary 5.11 that η is also a -map and thus ρ̄ is a -congruence. However ρ̄ is also an entourage of by Lemma 5.9, so it is cofinite congruence on .

Conversely, let σ be any cofinite congruence on . Then the restriction ρ = σ ∩(G×G) is a cofinite congruence on G, and as in the proof of Lemma 5.9, ρ̄ = σ.

### Corollary 6.11

Let G be a cofinite groupoid and equip Ḡ with its unique topological groupoid structure such that G is a uniform subgroupoid. If H is a compact Hausdorff topological groupoid and φ: GH is a uniformly continuous homomorphism, then the unique continuous map φ̄: H extending φ is a homomorphism of groupoids.

Proof

The set C = {(g, h) ∈ (2) | φ̄(gh) = φ̄(g)φ̄(h)} is a closed subset of (2) containing G(2). So, by Lemma 6.7, C = (2) and hence φ̄ is a homomorphism.

6.4. Cofinite Groupoids with Finite Vertex Sets

We will see that cofinite groupoids with only finitely many vertices behave very much like cofinite groups in many regards. To start with, we make a convenient definition.

We say that a congruence ρ on a groupoid G is rigid if its restriction to V (G) is trivial; i.e., ρ ∩ [V (G) × V (G)] = δV(G). In this case, if (g, h) ∈ ρ, then s(g) = s(h) and t(g) = t(h). In particular, when ρ is rigid, the natural map ν : GG/ρ has the property that ν[(G(3)] = (G/ρ)(3), and so (as in the proof of Theorem 6.8) G/ρ has a unique groupoid structure such that ν : GG/ρ is a homomorphism (and it is bijective on the vertex sets).

There is an equivalent alternative approach to rigid congruences using normal subgroups. Notice that if ρ is a rigid congruence on a groupoid G, then for each xV (G), the congruence class ρ[x] is a normal subgroup of the vertex group G(x, x) and this family (ρ[x])x∈V (G) is coherent in the following sense: if gG, then ρ[s(g)]g = ρ[t(g)] (where ρ[s(g)]g = g1ρ[s(g)]g). Conversely, if (Nx)x∈V (G) is any coherent family of normal subgroups of G, then there is a unique rigid congruence ρ on G such that ρ[x] = Nx for all xV (G); it is defined by (g, h) ∈ ρ if and only if s(g) = s(h), t(g) = t(h), and gh1Ns(g) (or equivalently, g1hNt(g)).

In order for a groupoid to have rigid congruences of finite indexes, its vertex set must be finite. And in this case, we make the following very useful observation.

### Lemma 6.12

Let G be a cofinite groupoid with a finite vertex set. Then the set of rigid cofinite congruences on G is a base for its uniformity.

Proof

We are assuming that G is non-empty as the assertion is trivial in the case where G is empty. Since G is Hausdorff, its finite vertex set V (G) is a discrete subset of G. So for each xV (G), there exists a cofinite congruence ρx on G such that ρx[x] ∩ V (G) = {x}. Then the finite intersection σ = ∩x∈V (G)ρx is a cofinite congruence on G and it is rigid. Consequently, the set of all ρσ, where ρ runs through all cofinite congruences on G, is a base for the uniformity on G consisting of rigid cofinite congruences.

Extending a property of cofinite groups, we next observe that every cofinite groupoid with only finitely many vertices is completely determined by its topological groupoid structure.

### Proposition 6.13

Let G be a topological groupoid with a finite vertex set. Then G has a uniformity making it into a cofinite groupoid and inducing its topology if and only if each G(x, y) is an open subset of G and each vertex group G(x, x) is a cofinite group, for x, yV (G). Moreover, in this case, such a uniformity on G is unique.

Proof

Suppose that the G(x, y) are open and that the G(x, x) are cofinite groups. By taking one component at a time, we may assume that the underlying directed graph of G is connected; i.e., that G(x, y) is non-empty for all x, yV (G). Fix xV (G). Then for each open normal subgroup N of G(x, x), we claim that there is a unique rigid congruence of finite indexes ρN on G such that ρN[x] = N. We construct ρN by forming a coherent family of normal subgroups NyG(y, y), yV (G). For each yV (G), choose gG(x, y) and put Ny = Ng. Note that Ny does not depend on the choice of g since N is a normal subgroup of G(x, x). Let ρN be the corresponding rigid congruence on G with ρ[y] = Ny for each vertex y. In particular, ρ[x] = Nx = N and it is clear that ρN is the unique such congruence on G. Furthermore, ρN has finite index. Indeed, if we make a choice of gyG(x, y) for each yV (G), then every congruence class is of the form $ρN[gy-1ggz]=gy-1ρN[g]gz=gy-1(gN)gz$ for some y, zV (G) and gG(x, x). Thus, if G has n vertices, then the index of ρN is n2 times the index of N in G(x, x). For later use, also note that each congruence class of ρN is an open subset of G since the cosets gN are open in G(x, x) and we are assuming that each G(x, y) is open in G.

Note that B = {ρN | N is an open normal subgroup of G(x, x)} is a base for a uniformity on G. Indeed, if N1 and N2 are open normal subgroups of G(x, x), then so is N1N2 and ρN1∩N2 = ρN1 ρN2 . We claim that this uniformity induces the topology on G. Let U be an open subset of G and let gU. Put y = s(g) and z = t(g) so that gG(y, z). Choose gyG(x, y) and gzG(x, z). Then $gyggz-1∈G(x,x)$. Since we are assuming that G(y, z) is open in G, we may assume that UG(y, z) and so $gyUgz-1$ is an open subset of G(x, x) containing $gyggz-1$. However G(x, x) is a cofinite group, and so there exists an open normal subgroup N such that $gyggz-1N⊆gyUgz-1$. Since $gyggz-1N=ρN[gyggz-1]=gyρN[g]gz-1$, it follows that ρN[g] ⊆ U and hence U is open in the uniform topology generated by our base B. On the other hand, as previously noted, every congruence class ρN[g], where N is an open normal subgroup of G(x, x) and gG, is open in G. Hence the uniform topology generated by B is equal to the topology on G, as claimed.

We have seen that the topology on G is generated by a uniformity with a base consisting of congruences of finite indexes on G. It remains to check that G is Hausdorff. But this follows easily by noting that G is the disjoint union of the open subsets G(y, z), y, zV (G), and each G(y, z) is homeomorphic to G(x, x) which is Hausdorff (being a cofinite group).

Conversely assume that G has a cofinite groupoid structure. By Proposition 6.6, each vertex group G(x, x) is a cofinite group. By Lemma 6.12, there exists a rigid cofinite congruence σ on G. Then for all gG(x, y), we see that σ[g] ⊆ G(x, y), and so each G(x, y) is open in G.

For the last part, consider any cofinite groupoid structure on G that induces its topology. By Lemma 6.12, this uniformity on G has a base, say C, consisting of rigid congruences of finite indexes on G. Given any ρC and xV (G), the congruence class N = ρ[x] is an open normal subgroup of G(x, x). By the uniqueness of such a rigid congruence, ρN = ρρ and ρNB. On the other hand, given any open normal subgroup N of G(x, x), there exists ρC such that ρ[x] ⊆ N (since N is also open in G and xN). Now ρ and ρN are rigid congruences with ρ[x] ⊆ ρN[x], and thus ρρN. It follows that C and B are bases for the same uniformity on G, and hence G has a unique cofinite groupoid structure that induces it topology.

Viewing groups as groupoids with a single vertex, we obtain the following result as an immediate corollary.

### Proposition 6.14

A Hausdorff topological group G is a cofinite group if and only if there is a uniformity on G with a base consisting of congruences of finite indexes on G that induces the topology on G. Moreover, in this case, such a uniformity on G is unique.

The following is a refinement of Theorem 6.8 for cofinite groupoids with finite vertex sets.

### Theorem 6.15

Let G be a cofinite groupoid with a finite vertex set. Then V () = V (G) and Ḡ admits a unique cofinite groupoid structure such that G is a uniform subgroupoid. Moreover, endowed with this structure, Ḡ is a profinite groupoid and the rigid cofinite congruences on Ḡ consist precisely of the closures ρ̄ of all rigid cofinite congruences ρ on G.

Proof

By Lemma 5.8, $V(G¯)=V(G)¯=V(G)$ (since a finite subset of a Hausdorff space is closed). The rest of the result follows from Theorem 6.8 and Corollary 6.10 since when V () = V (G), it is clear that a cofinite congruence ρ on G is rigid if and only if its closure ρ̄ is rigid.

6.5. The Fundamental Profinite Groupoid of a Profinite Graph

We conclude by briefly sketching an application of the theory of completions of cofinite groupoids which we explore in greater detail in a subsequent paper. Initially, let Γ be a finite discrete graph and let π1(Γ) be its fundamental groupoid (see, for instance, [6]). Endow π1(Γ) with the uniformity having a base consisting of all rigid congruences of finite indexes on π1(Γ). Note that for each vertex v of Γ, the vertex group based at v is the fundamental group π1, v), which is a free group. It is a well-known fact that free groups are residually finite. So, by the correspondence between coherent families of normal subgroups of finite indexes of the vertex groups and rigid congruences on π1(Γ), it follows that the π1(Γ) is Hausdorff (i.e., the intersection of all congruences of finite indexes is identity congruence on π1(Γ)) and thus a cofinite groupoid. (This is clearly the unique maximal cofinite groupoid structure on π1(Γ).) We call the completion of π1(Γ), endowed with the unique cofinite groupoid structure such that π1(Γ) is a uniform subgroupoid, the profinite fundamental groupoid of Γ and denote it by

$π^1(Γ)=π1(Γ)¯.$

Although this construction only requires the vertex set of Γ to be finite, we will only be applying it to finite graphs in what follows.

By Theorem 6.15, π̂1(Γ) is a profinite groupoid whose vertex set is V (π1(Γ)) = V (Γ).

Next let f : Γ → Δ be a map of finite graphs. We use the same symbol to denote the induced homomorphism f : π1(Γ) → π1(Δ); see [6] for more details on the fundamental groupoid functor. Then, by Corollary 6.11, the unique continuous extension of f is a homomorphism of groupoids which we denote by

$f^:π^1(Γ)→π^1(Δ).$

Moreover, if f : Γ → Δ and g: Δ → Ω are maps of finite graphs, then it is clear that $gf^=g^f^$. It is also clear that the identity map on Γ induces the identity homomorphism in π̂1(Γ). Thus we have defined a functor from the category of finite discrete graphs and maps of graphs to the category of profinite groupoids and continuous homomorphisms. We extend this functor to the entire category of profinite graphs and continuous maps of graphs as follows.

Let Γ be any profinite graph and let I be the set of all cofinite entourages of Γ. By Theorem 3.4, I is a base for the uniformity on Γ and it follows that $Γ=lim← ΓR$, the projective limit of the inverse system (ΓR, φRS) of finite discrete graphs and surjective maps of graphs indexed by the directed set I (partially ordered by reverse inclusion). Applying our profinite fundamental groupoid functor to this inverse system yields an inverse system of profinite groupoids and continuous homomorphisms (π̂1R), φ̂RS) indexed by the directed set I. We define the profinite fundamental groupoid of Γ to be the inverse limit (in the category of topological groupoids) of this system and denote it by

$π^1(Γ)=lim← π^1(ΓR).$

It should be noted that when Γ is a finite graph, this latter definition of π̂1(Γ) agrees with the former one above since in this case the singleton set {δΓ} is a cofinal subset of the directed set I, and thus $lim← π^1(ΓR)=π^1(Γ/δΓ)$and ΓΓ = Γ. Moreover, it easy to see that an inverse limit of profinite groupoids is also a profinite groupoid. Thus the profinite fundamental groupoid of any profinite graph is in general a profinite groupoid.

Turning to induced homomorphisms, we sketch a proof of the following result.

### Theorem 6.16

Let Γ, Δ be profinite graphs and let f : Γ → Δ be a continuous map of graphs. Then there is a unique continuous map f̂ : π̂1(Γ) → π̂1(Δ) such that for each pair R, S of cofinite graph entourages of Γ, Δ respectively with f(R) ⊆ S, the diagram

is commutative. Moreover, f̂ is a homomorphism of groupoids.

Let I, J be the set of all cofinite graph entourages of Γ, Δ respectively. Denote the canonical projection maps by φR : π̂1(Γ) → π̂1/R) and ψS : π̂1(Δ) → π̂1/S), for each RI and SJ.

### Step 1

For each SJ, there is a unique map S : π̂1(Γ) → π̂1/S) such that if RI and f(R) ⊆ S, then S = SR φ̂R. Moreover, being the composition of two continuous homomorphisms, S is also a continuous homomorphism.

Since f is uniformly continuous, we can choose RI such that f(R) ⊆ S. Thus it suffices to show that if R1,R2I and f(Ri) ⊆ S, then SR1 φ̂R1 = SR2 φ̂R2. To see this, let R = R1R2. Note that RI with RiR, and so SR1 φ̂R1 = SR1 φ̂R1R φ̂R. However, by the functorial properties of homomorphisms induced by maps of finite graphs, $f^SR1φ^R1R=fSR1φR1R^=f^SR$. Thus SR1 φ̂R1 = SR φ̂R. Similarly SR2 φ̂R2 = SR φ̂R, and step 1 is completed.

### Step 2

The family of maps ( S)S∈J is compatible with the inverse system (π̂1/S), ψ̂S1S2 ) and thus determines a unique continuous homomorphism : π̂1(Γ) → π̂1(Δ) such that ψS = S for all SJ.

Let S1S2 in J. Choose RI such that f(R) ⊆ S1S2. Then ψ̂S1S2 S2 = ψ̂S1S2 S2R φ̂R (by Step 1 since f(R) ⊆ S2). However, by the functorial properties of homomorphisms induced by maps of finite graphs, $ψ^S1S2f^S2R=ψS1S2fS2R^=f^S1R$. Thus ψ̂S1S2 S2 = S1R φ̂R = S1 (by Step 1 since also f(R) ⊆ S1).

Now by Steps 1 and 2, the homomorphism : π̂1(Γ) → π̂1(Δ) has the desired property.

It is now an easy exercise to show that the functorial properties hold in general for induced homomorphisms:

1. If i: Γ → Γ is the identity map on a profinite graph Γ, then î is the identity homomorphism on π̂1(Γ).

2. If Γ, Δ, and Ω be profinite graphs and $Γ→fΔ→gΩ$ are uniformly continuous maps of graphs, then $gf^=g^f^$.

References
1. Bourbaki, N (1966). General topology. Elements of Mathematics. Reading Mass: Addison-Wesley
2. Hartley, B (1977). Profinite and residually finite groups. Rocky Mountain J Math. 7, 193-217.
3. Kelley, J (1955). General topology. Toronto-New York-London: D. Van Nostrand Company, Inc
4. Ribes, L, and Zaleski, P (2000). Profinite groups. Berlin: Springer-Verlag
5. Serre, J-P (1980). Trees. Berlin, Heidelberg, New York: Springer Verlag
6. Stallings, JR (1983). Topology of finite graphs. Invent Math. 71, 551-565.
7. Wilson, J (1998). Profinite groups. Oxford: Oxford University Press