Maximal Groups in Free Burnside Semigroups

Alair Pereira do Lago

Oct 7, 1998

Let n ³ 1 and m ³ 1 be any integers. We show that a maximal group of a free Burnside semigroup satisfying xⁿ = x^n+m is a free Burnside group satisfying x^m = 1. Furthermore, we show that such a group is free over a generating set whose cardinality is the cyclomatic number of a graph associated to the \mathrel J-class containing the group and we describe such a generating set. We characterize these graphs in the case n = 1 and we extend classical results of McLean by computing the cardinality of the free Burnside semigroup for every m such that the cardinality of the free Burnside group satisfying x^m = 1 is known. If n ³ 3, this graph is a circuit and the maximal groups are cyclic groups of order m.

For every m ³ 2, we present examples with 2m-1 generators for n = 1 and for n = 2. Therefore, in these cases, we have infinite maximal groups for m large enough. Thus the \mathrel J-classes of these groups are infinite, these semigroups are not finite \mathrel J-above and the congruence class associated with an element of such an infinite \mathrel J-class is not recognizable. We will also present an example of a congruence class in the case n = 2 and m = 2 that has two different shortest words. Many properties that hold for n ³ 3 fail if n = 2 and m ³ 2.

To sum up, this work presents new and powerful techniques that allows us to prove important properties of the free Burnside semigroups for n = 2, an almost completely unknown case until now. In some sense, the case n = 2 presents the complexities of the cases n = 1 and n ³ 3 simultaneously. While the maximal groups are cyclic of order m for n ³ 3, they can have more generators and can be infinite for n £ 2. While there are exactly 2^|A|-1 \mathrel J-classes which in turn are easily characterized in the case n = 1, there are infinitely many \mathrel J-classes which are in turn difficult to be characterized for n ³ 2.

Chapter 1
Introduction

In this chapter, we will give a brief introduction on the problem that we are studying: the quest for structural informations on any free Burnside semigroup. Before presenting our main results in Section , such as the characterization of the maximal groups of free Burnside semigroups, we will give some basic definitions in Section  and briefly survey the state of the art in Section . In Section  we will give a presentation of the content of each chapter of this work and in Section  we will consider some connections with other areas of Computer Science.

1.1  Preliminary definitions

We will first give the definitions necessary to state precisely the results of our thesis.

Let A be a finite alphabet and let n and m be integers satisfying the restrictions n ³ 1 and m ³ 1. The set of words with letters in A (including the empty word 1) is denoted by A^* . The set of nonempty words is denoted A⁺. Let \mathordp be the relation {(x^n+m,xⁿ)\mathrel|x Î A⁺} and let ~ be the smallest congruence¹ that contains \mathordp. The congruence class of a word w Î A^* will be denoted by \mathord[w\tilde] and M will denote the set {\mathord[w\tilde]\mathrel|w Î A^*}. The canonical projection from A^* onto M induces the multiplication \mathord[u\tilde] ·\mathord[v\tilde] = \mathord[uv\tilde]. Therefore ( M, ·) is a monoid and, since \mathord[1\tilde] = {1}, ( M\{\mathord[1\tilde]}, ·) is a semigroup. They are respectively called the free Burnside monoid on A satisfying xⁿ = x^n+m and the free Burnside semigroup on A satisfying xⁿ = x^n+m . Since \mathord[1\tilde] = {1} for n > 0, we will study the free Burnside semigroups through the free Burnside monoids. If we allow n = 0, the monoid is also a group, called free Burnside group on A satisfying x^m = 1 The set A is called generating set of these free Burnside structures. Moreover, up to literal isomorphisms, these free Burnside structures depend only on the cardinality of A and on n and m. In this introduction, for any k Î \mathbbN, we will represent the free Burnside group satisfying x^m = 1 generated by a set of k generators by \mathord B
(k,m) and will represent the free Burnside monoid satisfying xⁿ = x^n+m generated by a set of k generators by \mathord M
(k,n,m).

Given any relation R Ì A^* ×A^*, the word problem associated with R is that of deciding whether or not two given words w and w¢ are congruent by the smallest congruence that contains R. In other words, it is the problem of deciding whether w = w¢ or whether there exist k ³ 1 and sequences of words x₁, ¼,x_k and y₁, ¼, y_k and z₁, ¼, z_k and w₁, ¼,w_k such that w = x₁y₁z₁ and x_i w_i z_i = x_i+1 y_i+1z_i+1 for i = 1,¼,k-1 and w¢ = x_kw_kz_k and (y_i,w_i) Î R ÈR^-1 for i = 1,¼,k. In our case, we are concerned with the relation \mathordp, which depends on n and m, and the word problem on M M is that of deciding whether or not x and y are in the same ~ -congruence class.

Consider the Green relations \mathrel J, \mathrel D, \mathrelÂ, \mathrel L and \mathrel H defined as usual. They are equivalences and, in particular, the \mathrel J-class of an element x is the class of all elements y that generate the same principal ideal MxM. The main definitions and properties of Green relations will be recalled in Section  of Chapter . A semigroup is called finite \mathrel J-above if its \mathrel J-classes are finite and, given a particular \mathrel J-class, there are finitely many \mathrel J-classes above, where the order is that induced by inclusion of the principal ideals.

1.2  History

We are now going to exhibit some structural properties on the free Burnside groups and semigroups. When |A| = 1, the free Burnside monoid  M is cyclic and finite. Its structure is very simple and we will thus suppose that |A| > 1 from now on.

The problem of determining whether a free Burnside group finitely generated is finite or not is extremely complex and was raised by Burnside in 1902. On that occasion, Burnside [] proved the finiteness of \mathord B
(k,m) for m £ 3. Of course \mathord B
(k,1) is trivial and therefore \mathordB_k,1 = 1. Since \mathord B
(k,2) is the direct product of k copies of \mathbbZ₂, we have \mathordB_k,2 = 2^k. According to a result of Levi and van der Waerden [], which can also be found in Chapter 18 of the classical book of M. Hall [],

\mathordB_k,3 = 3^{\binomk1+\binomk2+\binomk3} = 3^{[(m(m2+5))/ 6]}. In 1940, I.N.Sanov [] proved the finiteness of \mathord B
(k,m) for m = 4. M. Hall [] proved a similar result for m = 6 in 1958 and also proved that \mathordB_k,6 = 2^a3^{\binomb1+\binomb2+\binomb3} for a = 1 + (k-1)3^{\binomk1+\binomk2+\binomk3} and b = 1+(k-1)2^k.

On the other hand, always assuming k ³ 2, the infinity of \mathord B
(k,m) was proved for every odd m ³ 4381 by Novikov and Adyan [,] in 1968. In 1975, Adyan [,] improved the restriction to any odd m ³ 665. Note that this implies the infinity of \mathord B
(k,mi) for any integer i ³ 1 and any odd m ³ 665 because \mathord B
(k,m) is a homomorphic image of \mathord B
(k,mi). In order to prove the infinity of \mathord B
(k,m) except for a finite number of values of m, it would remain to prove the result when m is some power of 2. In 1992, two results were announced independently, Ivanov [] announced the proof of the infinity of \mathord B
(2,2⁴⁸) and Lysenok [] announced the proof of the infinity of \mathord B
(2,2¹³). It also follows from these works that the word problems on the corresponding free Burnside groups are decidable. This includes any odd m ³ 665 or m ³ 2¹³ any power of 2. As we have already seen, the infinity of \mathord B
(k,m) implies the infinity of \mathord B
(k,mi) for every integer i ³ 1 and therefore \mathord B
(k,m) is infinite for all k ³ 2 and m ³ 2¹³×665. Nevertheless, the solution of the word problem in \mathord B
(k,m) does not give a solution in \mathord B
(k,mi), to our present knowledge. In the complete versions of their papers, Ivanov [] showed the infinity of \mathord B
(k,m) for k ³ 2 and any m ³ 2⁴⁸ and Lysenok [] obtained it for any m ³ 8000. Lysenok also proved the decidability of the word problem for all m ³ 8000 and multiple of 16.

In order to classify the structure of the free Burnside semigroups satisfying xⁿ = x^n+m we need to consider three cases: n = 1, n = 2 and n ³ 3. Our main interest here is the case n = 2 for where the structure of the free Burnside semigroups was almost completely unknown until now.

We will comment the case n = 1 first. An idempotent semigroup - a free Burnside semigroup satisfying xⁿ = x^n+m when n = 1 and m = 1 - is finite and completely known [] since 1952. In fact, by this classical work of Green and Rees, fixed m ³ 1, we know that the free Burnside monoids \mathord M
(k,1,m) are finite if and only if the free Burnside groups \mathord B
(k,m) are finite. In particular, the semigroups are infinite for m ³ 8000 and finite for m £ 4. However, some finiteness properties still hold. For example, these monoids have exactly 2^|A|-1 \mathrel J-classes. It also follows from the work of Green and Rees that any maximal group in these semigroups must be a homomorphic image of a free Burnside group satisfying  \mathord B
(k,m) for m large enough. Nevertheless, only in 1990, with Kaourek and Polák's work [], one proved that these maximal groups are isomorphic to a free Burnside group. All these proofs strongly depend on n = 1 and cannot be easily extended for other values of n.

We will now consider the free Burnside semigroups in the case n ³ 2. Using the Thue-Morse words [] and the work of Brzozowski et al. [], we know that these free Burnside semigroups are infinite (we are considering |A| ³ 2) and have infinite J-classes. In 1970, I. Simon [] considered the free Burnside monoid satisfying \mathord M
(2,2,1) by two generators and proved that the `frame' of the \mathrelÂ-classes is a tree. These are practically the only known properties until now for the case n = 2. While these semigroups are infinite, Brzozowski conjectured that some properties of finiteness should remain true for the free Burnside semigroups. In particular, he conjectured that, for m = 1, any congruence class \mathord[w\tilde] is recognizable. Motivated by the conjecture of Brzozowski, the successive works of de Luca and Varricchio [,], McCammond [], do Lago [,], and Guba [,] lead to the discovering of many structural properties of free Burnside semigroups for n ³ 3 and m ³ 1. The reader is referred to our work [] to have an account of all the history and the proofs of these properties. In fact, given \mathordp, we effectively produce a rewriting system \mathordS and we show that the congruences generated by \mathordS and by \mathordp are equal if n ³ 2. (A reader interested in an introduction on rewriting systems can read, for example, the surveys of Huet [] or Klop [].) We define a property for \mathordS, called stability, and we show that \mathordS is stable when n ³ 3 and m ³ 1. The following properties can be deduced from the stability of \mathordS, without any other hypothesis on the values of n and of m:

1. \mathordS is a rewriting system with the Church-Rosser property;
2. the word problem is decidable;
3. there exists a unique shortest word in each congruence class;
4. the `frame' of the \mathrelÂ-classes is a tree;
5. there exists a characterization of the \mathrel and \mathrel L-classes;
6. there exists a characterization of the regular \mathrel D-classes and of the irregular ones;
7. the irregular \mathrel H-classes are all trivial;
8. the maximal groups are cyclic of order m;
9. the semigroup is finite \mathrel J-above;
10. the conjecture of Brzozowski is true.

1.3  Our results

The main result of this work is a property that holds for any n ³ 1 and any m ³ 1. We show that a maximal group of a free Burnside semigroup satisfying xⁿ = x^n+m is a free Burnside group satisfying x^m = 1. This contains the results of Kaourek and Polák that studied the case n = 1. Furthermore, we show that such a group is free over a generating set whose cardinality is the cyclomatic number of a graph associated to the \mathrel J-class containing the group and we present an explicit description of such a generating set. As a consequence of the characterization of the fundamental graphs in the case n = 1, we extend the result of McLean [] and we compute the cardinality of the free Burnside monoid for every m in which the cardinality of any free Burnside group satisfying x^m = 1 is known. If \mathordS is stable (in particular, for n ³ 3), this graph is a circuit and the maximal groups are cyclic groups of order m.

Our proof holds for any n ³ 1 and any m ³ 1. This is particularly interesting because the previous techniques could only be applied to the particular cases for which they have been designed.

For every m ³ 2, we present examples with 2m-1 generators for n = 1 and for n = 2. Therefore, in these cases, we have infinite maximal groups for m large enough. This immediately implies that the \mathrel J-classes of these groups are infinite, that these semigroups are not finite \mathrel J-above and also that the congruence class associated with an element of such an infinite group is not recognizable. We will also present an example of a congruence class, in the case n = 2 and m = 2, that has two different shortest words. Many properties that hold if \mathordS is stable fail if n = 2 and m ³ 2.

The search for such examples in the case n = 2 required powerful computational resources. Nevertheless, all statements relative to these examples will be proved here.

To sum up, this work presents new and powerful techniques that allows us to prove important properties of the free Burnside semigroups for n = 2, an almost completely unknown case until now. In some sense, the case n = 2 combines the complexities of the cases n = 1 and n ³ 3 simultaneously. While the maximal groups are cyclic of order m for n ³ 3, they can have more generators and can be infinite for n £ 2. While there are exactly 2^|A|-1 \mathrel J-classes which are in turn easily characterized in the case n = 1, there are infinite \mathrel J-classes which are in turn difficult to characterize for n ³ 2.

1.4  Overview

In Chapter  we will introduce the usual definitions of graph theory required in our work. These concept will first be applied to categories and groupoids, that will be studied and defined in Chapters  and . Later on, they will appear in the study of the fundamental graph of a \mathrel D-class, in Section  of Chapter . These graphs can possibly be infinite. Unfortunately, most of the available literature on graph theory only consider finite graphs. Thus, after the definitions of Section , we will see in Section  some elementary results of graph theory, that do not suppose any restriction on the cardinalities of the graphs. These elementary results do not consider infinite paths, that often occurs in the theory of infinite graphs, and are necessary to the correct definition of the concept of the cyclomatic number of a graph, in Section . This concept of cyclomatic number will appear in important results of our work, as in Theorems  and .

In Chapter , we will introduce the definitions of categories and groupoids required in our work. The concept of category generalizes that of monoid and we will extend to categories various concepts already known in monoid theory, such that congruences. Our purpose was not, at the beginning, the study of categories and groupoids, but the structure of the free Burnside monoids. During this study, some graphs appeared naturally - as the fundamental graph of a \mathrel D-class as it will be seen in Section  of Chapter  - and some categories - as the free category generated by a graph and the free Burnside groupoid generated by this graph. We thought it was useful to explicit these concepts. Furthermore, some of our results, expressed in the language of categories, could be sufficiently interesting from the point of view of category theory and groupoids. It is the case for Theorem  in Chapter . The reader may find more informations on categories in the classical book of MacLane [] and important results connecting category theory with monoid theory in Tilson's work [].

In Chapter , we will define a special groupoid: the free Burnside groupoid satisfying x^m = 1 generated by a strongly connected graph. The main result of the chapter, Theorem , states that the local groups of this groupoid are all isomorphic to the same free Burnside group, satisfying x^m = 1. We also exhibit a generating set for this free group. After some general definitions given in Section , in Sections  and  we give the definitions and the results required to the proof of Theorem  for m ³ 2. This proof is in turn done in Section .

In Chapter , we focus our attention on the free Burnside monoid itself. Nevertheless, the definitions and the results occurring in this chapter require less hypotheses: we only suppose that the monoid in question is stable. This generality holds in particular for the most important result in this chapter: Lemma . In Section , we will give the preliminary definitions of the chapter and we will define the Green-induced relations, that give to the free monoid A^* a structure induced by the Green relations on the monoid M and by a morphism from A^* onto M. In Sections  and  we will give important definitions like \mathrel D-entrances and transitions. As the reader will see in Section  of Chapter , the definition of the fundamental graph of a \mathrel D-class of a free Burnside monoid relies heavily on these concepts. In Section , an important application of the transitions of a word: Lemma  mentioned above. This lemma will be used in the proof of Theorem .

In Chapter  we will consider the free Burnside monoid satisfying xⁿ = x^n+m generated by an alphabet A, for integers n ³ 1 and m ³ 1. After the definition in Section , we will present the markers theorem (Theorem ) in Section , that shows that a property of the idempotent semigroup holds also for any free Burnside monoid. This result was, in essence, known since 1970, when I. Simon [] obtained some properties of the free Burnside semigroup satisfying x² = x³ generated by two generators. In Section  we will see the definition of a central concept in our work: the fundamental graph of a \mathrel D-class of a free Burnside monoid. The fundamental graph is strongly connected, as we will see in Proposition  and we will be able to define the free Burnside groupoid satisfying x^m = 1 generated by this graph. Some connected concepts and properties will be discussed. For instance, we will associate to a word w a path in the fundamental graph of the \mathrel D-class of \mathord[w\tilde]. This is the fingerprint of w, a fundamental concept for deciding whether or not two words projected in the same \mathrel D-class are congruent, as we will see in Theorem  in Chapter . We also give a construction of the smallest word that has a certain fingerprint and this construction will be crucial for the proof of the existence of a congruence class with two shortest words, given in Chapter . In Section , we will prove some properties relative to the regularity of a \mathrel D-class of a free Burnside monoid. In particular, in Proposition , we will see that the irregular \mathrel H-classes are trivial and in Proposition , we show that any fundamental graph of an irregular \mathrel D-class does not have any edge and has a unique vertex.

In Chapter  we will prove two of the most important results of this work: the characterization theorem (Theorem ) and the maximal groups theorem (Theorem ). In the proof of the characterization theorem, we will use various concepts introduced in the work. For instance, the fundamental graph of a \mathrel D-class and the free Burnside groupoid satisfying x^m = 1 generated by this graph. This theorem characterizes when two words projected in the same \mathrel D-class are congruent by the Burnside congruence. This characterization depends on the knowledge of the fundamental graph of the \mathrel D-class in question. On the other hand, in Section , we will see the maximal groups theorem. Not only this theorem uses the characterization theorem in its proof, but also it uses Theorem  from Chapter . Theorem  states that a maximal group in a free Burnside semigroup satisfying x^n+m = xⁿ is a free Burnside group satisfying x^m = 1. Note that this result is in conformity with those already known for n ³ 3 and m ³ 1. Indeed, Theorem 8.16 [] states that any maximal group is cyclic of order m (the free Burnside group satisfying x^m = 1 generated by a unique element). There is a substantial progress in the maximal groups theorem because it holds for any n ³ 1 and m ³ 1, and the cases n = 1 and n = 2 have a very different structure from that seen for n ³ 3 and m ³ 1. In the general case, the generating set of the free Burnside group may have more than one, contrary to the case n ³ 3 and m ³ 1. Furthermore, we give a generating set for this free Burnside group and prove that the cardinality of this set is the cyclomatic number of the fundamental graph of the \mathrel D-class that contains the maximal group in question. This difference proves to be relevant because in Theorem , in Chapter , we exhibit a regular \mathrel D-class whose fundamental graph has cyclomatic number 2m-1 at least.

In Chapter , we present the example of a regular \mathrel D-class of the free Burnside monoid satisfying x² = x^2+m generated by an alphabet of two letters whose fundamental graph has cyclomatic number 2m-1 at least. As a consequence, Theorem  implies that the maximal groups of this \mathrel D-class are free Burnside groups satisfying x^m = 1 with at least 2m-1 generators. As discussed before, for m large enough, we know that these groups are infinite since they have at least two generators. Proposition  of Chapter  now implies that every congruence class whose canonical projection is mapped onto an element of this \mathrel D-class with infinite \mathrel H-classes is not recognizable. Finally, we will see an example of a congruence class with two shortest words. All these results contrast with the case of a free Burnside monoid satisfying xⁿ = x^n+m with n ³ 3 and m ³ 1. Indeed, in these cases, the maximal groups have a unique generator (Theorem 8.16 []), every congruence class is recognizable (Theorem 8.18 []) and has a unique shortest word (Theorem 7.3 []).

In Chapter , we will apply the main results of this work to free Burnside semigroups whose structures are sufficiently known. We will study the cases n = 1 and n ³ 3. In Section  we consider the case n = 1 and we characterize the fundamental graph of a \mathrel D-class of a free Burnside semigroup satisfying x = x^m+1 in Theorem . In particular, we compute its cyclomatic number. If the cardinality of the Burnside group \mathord B
(k,m) is known for every integer k ³ 1, we compute in Corollary  the cardinality of each \mathrel J-class of M - and therefore the cardinality of the Burnside monoid M itself. This gives the cardinality of M in function of |A| in the cases m £ 3, for example. In 1954, McLean [] gave a description of the cardinality of \mathord M
(()k,1,1) (free band with k generators). We generalize this result for any m ³ 1 in which the cardinality of \mathord B
(k,m) is known. For m large enough and three generators in A at least, we verify that in M there exists a \mathrel J-class with infinitely many \mathrelÂ-classes and \mathrel L-classes. Furthermore, every \mathrel H-class in this \mathrel J-class is a free Burnside group satisfying x^m = 1 generated by an infinite set of generators. In Corollary , we see a result of Kaourek and Polák [] that reduces the word problem on M to the word problem on a free Burnside group \mathord B
(k,m) for k finite. This implies that the word problem is decidable on M even if M is infinite, as in the cases where m ³ 665 is odd or m ³ 8000 is a multiple of 16. In Section , we assume n ³ 1 and m ³ 1 and we give a new proof of Theorem 8.16 [] that states that the maximal groups of a free Burnside semigroup satisfying xⁿ = x^n+m are all cyclic of order m when n ³ 3. In this way, we characterize in Theorem  the fundamental graph of a regular \mathrel D-class of the free Burnside semigroup and we prove that it is a circuit.

1.5  Connections with other areas

To conclude this introduction, we would like to point out some connections and motivations of this area, related to Computer Science. The study of periodicities in words appears in many important areas of Computer Science such as, for instance, pattern matching and searching algorithms. The Burnside structures are defined by equations that impose the equivalence of certain powers of words in any context as we have just seen. This work, together with previous works, shows that these Burnside structures behave very differently, depending on the quantity of periods involved (measured by the values of m and of n). In sight of the variations, the understanding of the underlying combinatorics is an intriguing adventure and can also put some light on the understanding of other questions of Computer Science that depend on periods.

Given R Í A^* ×A^*, recall that the word problem associated to R is undecidable in general, even for R finite. In our case, the relation R is \mathordp, which depends on n and m, and the answer to this word problem depends strongly on the values of n and m, as described previously.

An important consequence of the conjecture of Brzozowski is an application that allows an easy solution of the word problem. In fact, if we constructively prove the conjecture of Brzozowski, we have a finite automaton, which depends on the given words, which solves this instance of the word problem. This includes the cases where n ³ 3. Unfortunately, if n = 1 or n = 2, the conjecture of Brzozowski does not hold for almost all values of m. Nevertheless, it may be still possible to solve the word problem on \mathord M
(k,n,m) for k ³ 2. Suppose that the fundamental graph of the projection of any word x in \mathord M
(k,n,m) can be effectively obtained and that the word problem is decidable on \mathord B
(k,m). Then an application of Theorem  implies that the word problem is decidable on \mathord M
(k,n,m). In particular, this holds when n = 1 and m is odd and large enough, although the conjecture of Brzozowski does not hold in this case. For cases as n = 2, the word problem is still open.

Chapter 2
Graphs and Trees

In this chapter we will introduce the usual definitions of graph theory required in our work. These concept will first be applied to categories and groupoids, that will be studied and defined in Chapters  and . Later on, they will appear in the study of the fundamental graph of a \mathrel D-class, in Section  of Chapter . These graphs can possibly be infinite. Unfortunately, most of the available literature on graph theory only consider finite graphs. Thus, after the definitions of Section , we will see in Section  some elementary results of graph theory, that do not suppose any restriction on the cardinalities of the graphs. These elementary results do not consider infinite paths, that often occurs in the theory of infinite graphs, and are necessary to the correct definition of the concept of the cyclomatic number of a graph, in Section . This concept of cyclomatic number will appear in important results of our work, as in Theorems  and .

Our approach on the graphs will emphasize its set of edges, if we compare with the usual theory of graphs. The vertices practically are only useful to characterize the consecutivity or not of two edges. Our graphs are directed.

2.1  Graphs, paths and strict paths

A directed graph , or simply graph , is a tuple (V,E,a,w) where V and E are any sets endowed with two functions a: E ®V and w: E ®V. Each element of E is called edge of \protect\mathordG and each element of V is called vertex of \protect\mathordG . The set \mathord E
(\mathordG) = E is called set of edges of \protect\mathordG , the set \mathord V
(\mathordG) = V is called set of vertices of \protect\mathordG . The functions a and w are called beginning and end respectively and are also generally called incidence functions .

We refer to the cardinality of \mathordG as the cardinality |\mathord E
(\mathordG)| of its set of edges. In our work, we will not do a priori any restriction on the cardinalities of the graphs and, usually, not we will have any isolated vertex (vertex without the incidence of any edge). Normally we will confuse the graph \mathordG with its set of edges \mathord E
(\mathordG) leaving implicit the functions beginning, end and the set of vertices \mathord V
(\mathordG). When the set of vertices is not explicit, we will be assuming \mathord V
(\mathordG) = \mathord ( a)
(\mathordG) È\mathord ( w)
(\mathordG) where \mathord ( a)
(\mathordG) denotes the set \mathord ( a)
(\mathord E
(\mathordG)) and \mathord ( w)
(\mathordG) denotes the set \mathord ( w)
(\mathord E
(\mathordG)). We will denote that b is an edge of the graph \mathordG by b Î \mathordG. Given two distinct graphs, frequently we will allow the using of the same symbols a and w to denote the functions beginning (or end) of both.

Let \mathordG be a graph. Two edges x,y Î \mathordG are called consecutive (and in this order) if \mathord ( w)
(x) = \mathord ( a)
(y). We call path in \protect\mathordG or simply path every finite sequence of consecutive edges of \mathordG. On each path p = b₁ b₂ ¼b_k, k ³ 1 we define the beginning of the path \mathord ( a)
(p) = \mathord ( a)
(b₁) and the end of the path \mathord ( w)
(p) = \mathord ( w)
(b_k). For each vertex v Î \mathord V
(\mathordG) we define \mathord1_v an empty path local to v , with beginning and end at the v. The length of a path is the size of the sequence of edges, where the length of the empty paths is 0. We say that two paths p,q are consecutive (and in this order) if \mathord ( w)
(p) = \mathord ( a)
(q). Given two consecutive paths p and q we define its concatenation pq naturally. Note that pq starts in \mathord ( a)
(p) and ends in \mathord ( w)
(q). It is not defined the concatenation of non-consecutive paths. Note that if p, q and r are consecutive paths in this order, then (pq)r = p(qr), that is equivalent to to say that the operation partial of the concatenation of paths is associative when all concatenations are defined. When p is a path that starts and ends in the same vertex v we say that p is a closed path on v or simply a closed path . An edge with same beginning and end is called loop . A graph \mathordG is called strongly connected we have at least a vertex and if, for every ordered pair of vertices, there exists a path with beginning at the first vertex and end at the second. Note that the smallest strongly connected graph is the graph with a unique vertex and no edges.

Given a path p = b₁b₂ ¼b_k, with k ³ 0, the set of internal vertices of p is {\mathord ( w)
(b₁),\mathord ( w)
(b₂),¼,\mathord ( w)
(b_k-1)}. We say that p is a strict path if the visited vertices are always distinct; that is to say, for every 1 £ i,j £ k we have that \mathord ( w)
(b_i) = \mathord ( a)
(b_j) Ûi = j-1. Note that this path may not be closed unless it is a empty path. Two paths p,q are called coterminal if have same beginning and same end. Given a path p = b₁b₂ ¼b_k there always exists a subsequence of p that is a strict path coterminal to p. A simple algorithm for the quest for such a strict path is the following: while there exist i and j (with 1 £ i,j £ k and i ¹ j-1) such that \mathord ( w)
(b_i) = \mathord ( a)
(b_j) removes from p the nonempty subsequence b_i+1 ¼b_j-1 if i < j or the nonempty subsequence b_j ¼b_i if i ³ j. After each of these removings, p is still a path with the same beginning and end. This algorithm in fact stops since the removings made to each step are nonempty and finally of the algorithm the path satisfies the necessary condition to be a strict path. Such a strict path that is subsequence of the path p will be called a strict path associated to the path p . Given two vertices v,u we say that the distance from v to u is the length of the shortest path that starts in v and ends in u.

2.2  Spanning trees

Given two graphs \mathordT and \mathordG we say that \mathordT is a subgraph of \protect\mathordG if \mathord V
(\mathordT) Í \mathord V
(\mathordG), if \mathord E
(\mathordT) Í \mathord E
(\mathordG) and if the incidence functions of \mathordT are natural restrictions of the incidence functions of \mathordG. In this case, we denote \mathordT Í \mathordG and \mathord ( a)
(\mathordT) È\mathord ( w)
(\mathordT) Í \mathord V
(\mathordT) Í \mathord V
(\mathordG). Besides, if \mathord ( a)
(\mathordT) È\mathord ( w)
(\mathordT) = \mathord V
(\mathordT), we say that \mathordT is the subgraph of \protect\mathordG induced by \protect\mathord E
(\mathordT) , with \mathord E
(\mathordT) Í \mathord E
(\mathordG). Given the graphs \mathordT Í \mathordG we denote by \mathordG \\mathordT the subgraph of \mathordG induced by the edges \mathord E
(\mathordG) \\mathord E
(\mathordT).

Let \mathordT be a subgraph of \mathordG and let v Î \mathord V
(\mathordT) Í \mathord V
(\mathordG) be a vertex. We will denote by \mathord ( w_v)
(\mathordT) Í \mathord V
(\mathordT) the set of ends of the paths in \mathordT that start in v (using edges only of \mathordT) and by \mathord ( a_v)
(\mathordT) Í \mathord V
(\mathordT) the set of beginnings of the paths in \mathordT that end in v. We say that \mathordT is a tree with beginning v if there exists only one path in \mathordT from v to any vertex of \mathord V
(\mathordT) and we say that \mathordT is a tree with end v if there exists only one path in \mathordT of any vertex from \mathord V
(\mathordT) to v. We say that \mathordT is a tree with root v if \mathordT is a tree with beginning v or a tree with end v. We say that \mathordT is a tree if there exists v Î \mathord V
(\mathordG) such that \mathordT is a tree with root v and we say that \mathordT is a spanning tree of \protect\mathordG (or simply spanning tree if \mathordG is evident) if \mathordT is a tree and if \mathord V
(\mathordT) = \mathord V
(\mathordG).

Let \mathordG be a graph with incidence functions a and w and let \mathordT Í \mathordG and V Í \mathord V
(\mathordT) Í \mathord V
(\mathordG). We say that a is injective in \protect\mathordT or establishes an injection on \protect\mathordT if its restriction to \mathordT is injective and we say that a is a bijection from \protect\mathordT to V or establishes a bijection from \protect\mathordT to V if it it is injective in \mathordT and if \mathord ( a)
(\mathordT) = V. The same terminology will be used for w.

We will present some elementary results of graph theory that, however, are only stated for finite graphs usually. In our hypotheses, the graphs can be infinite. Even non-enumerable. These results are necessary to the correct definition of the cyclomatic number of a graph.

[ 1 Take \mathordG a graph, v Î \mathord V
(\mathordG) a vertex and \mathordT Í \mathordG a tree with beginning v. Then

Proof.By definition, \mathord ( a)
(\mathordT),\mathord ( w)
(\mathordT), \mathord ( w_v)
(\mathordT) Í \mathord V
(\mathordT). As \mathordT is a tree with beginning v, we have that v Î \mathord V
(\mathordT). Furthermore, there exists a path from v to any vertex of \mathord V
(\mathordT) and therefore \mathord V
(\mathordT) Í \mathord ( w_v)
(\mathordT). Note, every path that starts in v or is empty and therefore ends in v, or has a last edge and therefore ends in a vertex of \mathord ( w)
(\mathordT). Therefore, \mathord ( w_v)
(\mathordT) Í \mathord ( w)
(\mathordT)È{v}.

Note that we can formulate a dual result to the of Proposition  for trees with end v. We emphasize that the graph \mathordG in question may be infinite, and even non-enumerable. Statement  implies that the cardinality of any spanning tree is always the same: |\mathord V
(\mathordG)| - 1.

[ 2 Take \mathordG a graph, v Î \mathord V
(\mathordG) a vertex, T Í \mathord E
(\mathordG) a set of edges and \mathordT the graph induced by T. Then the statements  and  are always equivalent and are equivalent to Statement  in the case where T is finite:

1. \mathordT is a tree with beginning v;
2. \mathord ( w_v)
   (\mathordT) = \mathord ( w)
   (\mathordT) È{v} and v \not Î \mathord ( w)
   (\mathordT) and w is injective in \mathordT;
3. |\mathord ( w_v)
   (\mathordT)| = |T| + 1.

Proof.Suppose that Statement 2.2 holds. We are going to prove that Statement 2.2 holds. By Proposition 2.2, \mathord ( w_v)
(\mathordT) = \mathord ( w)
(\mathordT) È{v}. Suppose by contradiction that there exists an edge a Î \mathordT such that \mathord ( w)
(a) = v. As \mathordT is a tree with beginning v, we can take p the unique path from v to \mathord ( a)
(a) in \mathordT and p and pap are two different paths from v to \mathord ( a)
(a) in \mathordT, a contradiction with \mathordT be a tree with beginning v. Thus v \not Î \mathord ( w)
(\mathordT). Suppose by contradiction that there exist two distinct edges a,a¢ Î \mathordT such that \mathord ( w)
(a) = \mathord ( w)
(a¢). Taking p and p¢ the two paths in \mathordT from v to \mathord ( a)
(a) and to \mathord ( a)
(a¢) respectively, p¢a¢ and pa are two different paths in \mathordT from v to \mathord ( w)
(a) and we have new contradiction. In this way w is injective in \mathordT.

Suppose that Statement 2.2 holds. We are going to prove that Statement 2.2 holds. Let u Î \mathord ( w_v)
(\mathordT). First we will prove, by induction on the distance d from v to u, that there is a unique path in \mathordT from v to u. If d = 0, since v \not Î \mathord ( w)
(\mathordT), only the empty path ends in v. We have the induction basis. We will now suppose that d > 0 and that the result is true for any vertices that are distant at most d-1 from v. Let p be any path in \mathordT from v to u and let q be a path of length d from v to u in \mathordT. As w is an injection on \mathordT, there exists only one edge a Î \mathordT that ends in u. As d > 0, the paths p and q are nonempty and q and p have the same last edge a. Thus pa^-1 and qa^-1 are two paths of v for the same vertex \mathord ( a)
(a). As qa^-1 has length d-1, the distance from v to \mathord ( a)
(a) is at most |qa^-1| = d-1. By the induction hypothesis qa^-1 = p a^-1 and therefore p = q. This shows that there is a unique path in \mathordT from v to any vertex of \mathord ( w_v)
(\mathordT). It is hence sufficient to prove that \mathord V
(\mathordT) Í \mathord ( w_v)
(\mathordT). As \mathord V
(\mathordT) = \mathord ( a)
(\mathordT) È\mathord ( w)
(\mathordT) for \mathordT being an induced subgraph, as \mathord ( w_v)
(\mathordT) = \mathord ( w)
(\mathordT) È{v} by hypothesis, to conclude the proof of that \mathordT is a tree with beginning v, it suffices to prove that \mathord ( a)
(\mathordT) Í \mathord ( w_v)
(\mathordT). Let x be any vertex of \mathord ( a)
(\mathordT) and let a Î \mathordT be an edge such that \mathord ( a)
(a) = x. Since \mathord ( w)
(a) Î \mathord ( w)
(\mathordT) Ì \mathord ( w_v)
(\mathordT), let p be the unique path from v to \mathord ( w)
(a). Since v \not Î \mathord ( w)
(\mathordT), we have that v ¹ \mathord ( w)
(a). Therefore p is nonempty and its last edge ends in \mathord ( w)
(a). As w is an injection on \mathordT, this last edge is a and the path pa^-1 starts in v and ends in x. Thus \mathord ( a)
(\mathordT) Í \mathord ( w_v)
(\mathordT), completing the proof of that \mathordT is a tree with beginning v.

Suppose now that T is finite. We are going to prove that the statements 2.2 and 2.2 are equivalent. Suppose that Statement 2.2 holds. As w is injective in \mathordT, we have |\mathord ( w)
(\mathordT)| = |\mathordT|. As v \not Î \mathord ( w)
(\mathordT), we have that

|\mathord ( w_v)
(\mathordT)| = |\mathord ( w)
(\mathordT) È{v}| = |\mathord ( w)
(\mathordT)| + 1 = |T|+1. Suppose now that Statement 2.2 holds. Either every path that starts in v is empty and therefore ends in v, or otherwise has a last edge and therefore ends in a vertex of \mathord ( w)
(\mathordT). Therefore \mathord ( w_v)
(\mathordT) Í \mathord ( w)
(\mathordT) È{v}. Since \mathord ( w)
(\mathordT) = \mathord ( w)
(\mathord E
(\mathordT)) = \mathord ( w)
(T), since |\mathord ( w_v)
(\mathordT)| = |T|+1 by hypothesis, always by argument of cardinality: the union \mathord ( w)
(\mathordT) È{v} is disjoint; |\mathord ( w)
(\mathordT)| = |T| and therefore w is an injection on \mathordT; and \mathord ( w_v)
(\mathordT) = \mathord ( w)
(\mathordT) È{v}.

Proposition  provides a characterization of strongly connected graphs in terms of spanning trees. This implies in particular that every strongly connected graph has a spanning tree.

[ 3 Let \mathordG be a graph. The following statements are equivalent:

1. The graph \mathordG is strongly connected;
2. There exists a vertex v Î \mathord V
   (\mathordG), a spanning tree \mathordT Í \mathordG with beginning v and a spanning tree \mathordT¢ Í \mathordG with end v;
3. \mathord V
   (\mathordG) is not empty and for every vertex v Î \mathord V
   (\mathordG), there exist a spanning tree \mathordT Í \mathordG with beginning v and a spanning tree \mathordT¢ Í \mathordG with end v.

Proof.Of course Item 2.2 implies Item 2.2.

We are going to show that Item 2.2 implies Item 2.2. Let v Î \mathord V
(\mathordG) be a vertex and let \mathordT,\mathordT¢ Í \mathordG be two spanning trees with beginning v and with end v respectively. Let x,y Î \mathord V
(\mathordG) be any two vertices. Taking p a path from x to v in the spanning tree \mathordT¢ and taking q a path from v to y in the spanning tree \mathordT the path pq is a path from x to y with beginning at the x and end at the y. Therefore, the graph \mathordG is strongly connected.

We are going to show that Item 2.2 implies Item 2.2. Suppose that the graph \mathordG is strongly connected. By definition, \mathord V
(\mathordG) ¹ Æ and we may choose v Î \mathord V
(\mathordG) any vertex. By definition, for each vertex u, we may choose a path from v to u. In particular, we may choose \mathordp_u, a path from v to u of smallest length. Of course the distance from v to u is |\mathordp_u|. Furthermore, when u ¹ v we have that \mathordp_u is nonempty and we may define \mathorda_u to be the last edge of \mathordp_u. We define \mathordT as the subgraph of \mathordG induced by {\mathorda_u\mathrel|u Î \mathord V
(\mathordG)\{v}}. Note that the function w is a bijection from \mathordT to \mathord V
(\mathordG) \{v}. We state that if u ¹ v then |\mathordp_u| = |\mathordp_{\mathord ( a)
(\mathordau)}|+ 1. In fact, being \mathordp_u \mathorda_u^-1 and \mathordp_{\mathord ( a)
(\mathordau)} two paths from v to \mathord ( a)
(\mathorda_u), from the minimality of \mathordp_{\mathord ( a)
(\mathordau)} we have that |\mathordp_{\mathord ( a)
(\mathordau)}| £ |\mathordp_u \mathorda_u^-1| = |\mathordp_u| - 1. Moreover, being \mathordp_u and \mathordp_{\mathord ( a)
(\mathordau)}\mathorda_u two paths from v to u, from the minimality of \mathordp_u we have that |\mathordp_u| £ |\mathordp_{\mathord ( a)
(\mathordau)}\mathorda_u| = |\mathordp_{\mathord ( a)
(\mathordau)}| + 1. This in the allows to make a inductive definition of a new path \mathordq_u that will be defined for every vertex u Î \mathord V
(\mathordG). The induction will be done on |\mathordp_u|. If |\mathordp_u| = 0 we have that u = v and we define \mathordq_u to be the empty path from v to v. If |\mathordp_u| > 0, having been defined all paths \mathordq_x for every vertex x such that |\mathordp_x| < |\mathordp_u|, we define \mathordq_u to be the path \mathordq_{\mathord ( a)
(\mathordau)}\mathorda_u. By a immediate induction on |\mathordp_u| we may prove that |\mathordq_u| = |\mathordp_u| and that \mathordq_u is a path from v to u in \mathordT. As for every vertex u Î \mathord V
(\mathordG) there exists a path \mathordq_u from v to u in \mathordT, we have that

\mathord ( w_v)
(\mathordT) = \mathord V
(\mathordG) = (\mathord V
(\mathordG) \{v}) + {v} = \mathord ( w)
(\mathordT)+ {v}. Using Proposition 2.2 \mathordT is a tree with beginning v and, therefore, a spanning tree with beginning v because \mathord ( w_v)
(\mathordT) = \mathord V
(\mathordG). Similarly we can construct a spanning tree with end v.

2.3  Cyclomatic number

In Proposition 2.2 we have seen that every strongly connected graph admits a spanning tree. In Proposition 2.2 we have seen that any spanning tree has the same cardinality |\mathord V
(\mathordG)|-1. The cyclomatic number of a strongly connected graph \mathordG is defined to be the cardinality

Proposition  relates the cyclomatic number of two strongly connected graphs when one of them, in particular, is a subgraph on the other.

[ 4 Let \mathordG be a strongly connected subgraph of a graph \mathordG¢ also strongly connected. Then the cyclomatic number of \mathordG is at most the cyclomatic number of \mathordG¢.

Proof.If \mathordG = \mathordG¢, there is nothing to be proved. Suppose therefore that \mathord E
(\mathordG¢) \\mathord E
(\mathordG) ¹ Æ.

Let v be a vertex of \mathordG. Since \mathordG is strongly connected, we may choose \mathordT Í \mathordG a spanning tree of \mathordG with beginning v due to Proposition 2.2. Let 0 be a vertex not belonging to \mathord V
(\mathordG¢) Ê \mathord V
(\mathordG) and let V = \mathord V
(\mathordG¢) \\mathord V
(\mathordG)+ {0}. Consider the function d: \mathord V
(\mathordG¢) ®V defined by