Algebraic Graph Theory Morphisms Monoids And Matrices 1st Edition Ulrich Knauer

Algebraic Graph Theory Morphisms Monoids And
Matrices 1st Edition Ulrich Knauer download
https://ebookbell.com/product/algebraic-graph-theory-morphisms-
monoids-and-matrices-1st-edition-ulrich-knauer-50378644
Explore and download more ebooks at ebookbell.com

Here are some recommended products that we believe you will be
interested in. You can click the link to download.
Algebraic Graph Theory Morphisms Monoids And Matrices 2 Rev And Ext Ed
Ulrich Knauer
https://ebookbell.com/product/algebraic-graph-theory-morphisms-
monoids-and-matrices-2-rev-and-ext-ed-ulrich-knauer-50378750
Algebraic Graph Theory 1st Edition Chris Godsil Gordon Royle Auth
https://ebookbell.com/product/algebraic-graph-theory-1st-edition-
chris-godsil-gordon-royle-auth-2413660
Algebraic Graph Theory Ulrich Knauer Kolja Knauer
https://ebookbell.com/product/algebraic-graph-theory-ulrich-knauer-
kolja-knauer-232954296
Topics In Algebraic Graph Theory 1st Edition Lowell W Beineke
https://ebookbell.com/product/topics-in-algebraic-graph-theory-1st-
edition-lowell-w-beineke-1276180

Isomorphisms Symmetry And Computations In Algebraic Graph Theory
Pilsen Czech Republic October 37 2016 Springer Proceedings In
Mathematics Statistics 1st Ed 2020 Gareth A Jones Editor
https://ebookbell.com/product/isomorphisms-symmetry-and-computations-
in-algebraic-graph-theory-pilsen-czech-republic-
october-37-2016-springer-proceedings-in-mathematics-statistics-1st-
ed-2020-gareth-a-jones-editor-11299804
Algebraic Structures And Graph Theory Irina Elena Cristea Hashem
Bordbar
https://ebookbell.com/product/algebraic-structures-and-graph-theory-
irina-elena-cristea-hashem-bordbar-54691940
Discrete Mathematics Graph Algorithms Algebraic Structures Coding
Theory And Cryptography Sriraman Sridharan R Balakrishnan
https://ebookbell.com/product/discrete-mathematics-graph-algorithms-
algebraic-structures-coding-theory-and-cryptography-sriraman-
sridharan-r-balakrishnan-10940474
Graphs In Perturbation Theory Algebraic Structure And Asymptotics 1st
Ed Michael Borinsky
https://ebookbell.com/product/graphs-in-perturbation-theory-algebraic-
structure-and-asymptotics-1st-ed-michael-borinsky-7321304
Essential Math For Ai Exploring Linear Algebra Probability And
Statistics Calculus Graph Theory Discrete Mathematics Numerical
Methods Optimization Techniques And More Ai Fundamentals Hinton
https://ebookbell.com/product/essential-math-for-ai-exploring-linear-
algebra-probability-and-statistics-calculus-graph-theory-discrete-
mathematics-numerical-methods-optimization-techniques-and-more-ai-
fundamentals-hinton-60355532

'H*UX\WHU6WXGLHVLQ0DWKHPDWLFV
(GLWRUV
&DUVWHQ&DUVWHQVHQ%HUOLQ*HUPDQ\
1LFROD)XVFR1DSROL,WDO\
)ULW]*HV]WHV\&ROXPELD86$
1LHOV-DFRE6ZDQVHD8QLWHG.LQJGRP
.DUO+HUPDQQ1HHE(UODQJHQ*HUPDQ\

8OULFK.QDXHU
$OJHEUDLF*UDSK7KHRU\
0RUSKLVPV0RQRLGVDQG0DWULFHV
'H*UX\WHU

0DWKHPDWLFDO6XEMHFW&ODVVL¿FDWLRQ&&&&&&
&&&&0000%%
,6%1
H,6%1
,661
/LEUDU\RI&RQJUHVV&DWDORJLQJLQ3XEOLFDWLRQ'DWD
.QDXHU8±
$OJHEUDLFJUDSKWKHRU\PRUSKLVPVPRQRLGVDQGPDWULFHVE\8OULFK.QDXHU
SFP±'H*UX\WHUVWXGLHVLQPDWKHPDWLFV
,QFOXGHVELEOLRJUDSKLFDOUHIHUHQFHVDQGLQGH[
,6%1DONSDSHU
*UDSKWKHRU\ $OJHEUDLFWRSRORJ\ ,7LWOH
4$.
±GF

%LEOLRJUDSKLFLQIRUPDWLRQSXEOLVKHGE\WKH'HXWVFKH1DWLRQDOELEOLRWKHN
7KH'HXWVFKH1DWLRQDOELEOLRWKHNOLVWVWKLVSXEOLFDWLRQLQWKH'HXWVFKH1DWLRQDOELEOLRJUD¿H
GHWDLOHGELEOLRJUDSKLFGDWDDUHDYDLODEOHLQWKH,QWHUQHWDWKWWSGQEGQEGH
‹:DOWHUGH*UX\WHU*PE+ &R.*%HUOLQ%RVWRQ
7\SHVHWWLQJ'D7H;*HUG%OXPHQVWHLQ/HLS]LJZZZGDWH[GH
3ULQWLQJDQGELQGLQJ+XEHUW &R*PE+ &R.**|WWLQJHQ
ƒƒ3ULQWHGRQDFLGIUHHSDSHU
3ULQWHGLQ*HUPDQ\
ZZZGHJUX\WHUFRP

Preface
This book is a collection of the lectures I have given on algebraic graph theory. These
lectures were designed for mathematics students in a Master’s program, but they may
also be of interest to undergraduates in the ﬁnal year of a Bachelor’s curriculum.
The lectures cover topics which can be used as starting points for a Master’s or
Bachelor’s thesis. Some questions raised in the text could even be suitable as sub-
jects of doctoral dissertations. The advantage afforded by the ﬁeld of algebraic graph
theory is that it allows many questions to be understood from a general mathematical
background and tackled almost immediately.
In fact, my lectures have also been attended by graduate students in informatics with
a minor in mathematics. In computer science and informatics, many of the concepts
associated with graphs play an important role as structuring tools – they enable us to
model a wide variety of different systems, such as the structure of physical networks
(of roads, computers, telephones etc.) as well as abstract data structures (e.g. lists,
stacks, trees); functional and object oriented programming are also based on graphs
as a means of describing discrete entities. In addition, category theory is gaining more
and more importance in informatics; therefore, these lectures also include a basic and
concrete introduction to categories, with numerous examples and applications.
I gave the lectures ﬁrst at the University of Bielefeld and then, in various incar-
nations, at the Carl von Ossietzky Universität Oldenburg. They were sometimes pre-
sented in English and in several other countries, including Thailand and New Zealand.
Selection of topics
The choice of topics is in part standard, but it also reﬂects my personal preferences.
Many students seem to have found the chosen topics engaging, as well as helpful and
useful in getting started on thesis research at various levels.
To mark the possibilities for further research, I have inserted many “Questions”, as
well as “Exercises” that lead to illuminating examples. Theorems for which I do not
give proofs are sometimes titled “Exerceorem”, to stress their role in the development
of the subject. I have also inserted some “Projects”, which are designed as exercises
to guide the reader in beginning their own research on the topic. I have not, however,
lost any sleep over whether to call each result a theorem, proposition, exerceorem,
or something else, so readers should neither deduce too much from the title given
to a result nor be unduly disturbed by any inconsistencies they may discover – this

vi Preface
beautiful English sentence I have adopted from the introduction of John Howie’sAn
Introduction to Semigroup Theory, published by Academic Press in 1976.
Homomorphisms, especially endomorphisms, form a common thread throughout
the book; you will meet this concept in almost all the chapters. Another focal point is
the standard part of algebraic graph theory dealing with matrices and eigenvalues. In
some parts of the book the presentation will be rather formal; my experience is that
this can be very helpful to students in a ﬁeld where concepts are often presented in an
informal verbal manner and with varying terminology.
Content of the chapters
We begin, in Chapter 1, with basic deﬁnitions, concepts and results. This chapter is
very important, as standard terminology is far from being established in graph theory.
One reason for this is that graph models are so extremely useful in a great number of
applications in diverse ﬁelds. Many of the modelers are not mathematicians and have
developed their own terminology and results, without necessarily caring much about
existing theory. Chapter 1 contains some new variants of results on graph homomor-
phisms and the relations among them, connecting them, in turn, to the combinatorial
structure of the graph.
Chapter 2 makes connections to linear algebra by discussing the different matrices
associated to graphs. We then proceed to the characteristic polynomial and eigenval-
ues, topics that will be encountered again in Chapters 5 and 8. There is no intention
to be complete, and the content of this chapter is presented at a relatively elementary
level.
In Chapter 3 we introduce some basic concepts from category theory, focusing on
what will be helpful for a better understanding of graph concepts.
In Chapter 4 we look at graphs and their homomorphisms, in particular binary
operations such as unions, amalgams, products and tensor products; for the latter two
operations I use the illustrative names cross product and box product. It turns out
that, except for the lexicographic products and the corona, all of these operations
have a category-theoretical meaning. Moreover, adjointness leads to so-called Mor
constructions; some of the ones presented in this chapter are new, as far as I know,
and I call them diamond and power products.
In Chapter 5 we focus on unary operations such as the total graph, the tree graph
and, principally, line graphs. Line graphs are dealt with in some detail; in particular,
their spectra are discussed. Possible functorial properties are left for further investi-
gation.
In Chapter 6, the fruitful notion of duality, known from and used in linear algebra,
is illustrated with the so-called cycle and cocycle spaces. We then apply the concepts
to derive Kirchhoff’s laws and to “square the rectangle”. The chapter ﬁnishes with a
short survey of applications to transportation networks.

Preface vii
Chapter 7 discusses several connections between graphs and groups and, more gen-
erally, semigroups or monoids. We start with Cayley graphs and Frucht-type results,
which are also generalized to monoids. We give results relating the groups to combi-
natorial properties of the graph as well as to algebraic aspects of the graph.
In Chapter 8 we continue the investigation of eigenvalues and the characteristic
polynomial begun in Chapters 2 and 5. Here we present more of the standard results.
Many of the proofs in this chapter are omitted, and sometimes we mention only the
idea of the proof.
In Chapter 9 we present some results on endomorphism monoids of graphs. We
study von Neumann regularity of endomorphisms of bipartite graphs, locally strong
endomorphisms of paths, and strong monoids of arbitrary graphs. The chapter in-
cludes a fairly complete analysis of the strong monoid, with the help of lexicographic
products on the graph side and wreath products on the monoid side.
In Chapter 10 we discuss unretractivities, i.e. under what conditions on the graph
do its different endomorphism sets coincide? We also investigate questions such as
how the monoids of composed graphs (e.g. product graphs) relate to algebraic com-
positions (e.g. products) of the monoids of the components. This type of question can
be interpreted as follows: when is the formation of the monoid product-preserving?
In Chapter 11 we come back to the formation of Cayley graphs of a group or semi-
group. This procedure can be considered as a functor. As a side line, we investigate
(in Section 11.2) preservation and reﬂection properties of the Cayley functor. This
is applied to Cayley graphs of right and left groups and is used to characterize Cay-
ley graphs of certain completely regular semigroups and strong semilattices of semi-
groups.
In Chapter 12 we resume the investigation of transitivity questions from Chapter 8
for Cayley graphs of strong semilattices of semigroups, which may be groups or right
or left groups. We start with Aut- and ColAut-vertex transitivities and ﬁnish with
endomorphism vertex transitivity. Detailed examples are used to illustrate the results
and open problems.
Chapter 13 considers a more topological question: what are planar semigroups?
This concerns extending the notion of planarity from groups to semigroups. We
choose semigroups that are close to groups, i.e. which are unions of groups with some
additional properties. So we investigate right groups and Clifford semigroups, which
were introduced in Chapter 9. We note that the more topological questions about
planarity, embeddings on surfaces of higher genus or colorings are touched on only
brieﬂy in this book. We use some of the results in certain places where they relate
to algebraic analysis of graphs – the main instances are planarity in Section 6.4 and
Chapter 13, and the chromatic number in Chapter 7 and some other places.
Each chapter ends with a “Comments” section, which mentions open problems and
some ideas for further investigation at various levels of difﬁculty. I hope they will
stimulate the reader’s interest.

viii Preface
How to use this book
The text is meant to provide a solid foundation for courses on algebraic graph theory.
It is highly self-contained, and includes a brief introduction to categories and functors
and even some aspects of semigroup theory.
Different courses can be taught based on this book. Some examples are listed be-
low. In each case, the prerequisites are some basic knowledge of linear algebra.
Chapters 1 through 8 – a course covering mainly the matrix aspects of algebraic
graph theory.
Chapters 1, 3, 4, 7 and 9 through 13 – a course focusing on the semigroup and
monoid aspects.
A course skipping everything on categories, namely Chapter 3, the theorems in
Sections 4.1, 4.2, 4.3 and 4.6 (although the deﬁnitions and examples should be
retained) and Sections 11.1 through 11.2.
Complementary to the preceding option, it is also possible to use this text as a
short and concrete introduction to categories and functors, with many (some-
what unusual) examples from graph theory, by selecting exactly those parts
skipped above.
About the literature
The literature on graphs is enormous. In the bibliography at the end of the book, I
give a list of reference books and monographs, almost all on graphs, orderedchrono-
logicallystarting from 1936; it is by no means complete. As can be seen from the
list, a growing number of books on graph theory are published each year. Works from
this list are cited in the text by author name(s) and publication year enclosed in square
brackets.
Here I list some books, not all on graphs, which are particularly relevant to this
text; some of them are quite similar in content and are cited frequently.
N. Biggs,Algebraic Graph Theory, Cambridge University Press, Cambridge
1996.
M. Behzad, G. Chartrand, L. Lesniak-Forster,Graphs and Digraphs, Prindle,
Weber & Schmidt, Boston 1979. New (ﬁfth) edition: G. Chartrand, L. Lesniak,
P. Zhang,Graphs and Digraphs, Chapman and Hall, London 2010.
D. Cvetkovi´c, M. Doob, H. Sachs,Spectra of Graphs, Academic Press, New
York 1979.
C. Godsil, G. Royle,Algebraic Graph Theory, Springer, New York 2001.
G. Hahn, G. Sabidussi (eds.),Graph Symmetry, Kluwer, Dordrecht 1997.

Preface ix
P. Hell, J. Nešetˇril,Graphs and Homomorphisms, Oxford University Press, Ox-
ford 2004.
H. Herrlich, G. Strecker,Category Theory, Allyn and Bacon, Boston 1973.
W. Imrich, S. Klavžar,Product Graphs, Wiley, New York 2000.
R. Kaschek, U. Knauer (eds.),Graph Asymmetries, Discrete Mathematics 309
(special issue) (2009) 5349–5424.
M. Kilp, U. Knauer, A. V. Mikhalev,Monoids, Acts and Categories, De Gruyter,
Berlin 2000.
M. Petrich, N. Reilly,Completely Regular Semigroups, Wiley, New York 1999.
D. B. West,Introduction to Graph Theory, Prentice Hall, Upper Saddle River,
NJ 2001.
Papers, theses, book chapters and other references are given in the text where they are
used.
Acknowledgements
This book was originally planned as a joint work with Lothar Budach. But the un-
timely death of Lothar, before we could really get started, cut short our collaboration.
First of all I thank the De Gruyter publishing house and especially the Mathematics
Editor Friederike Dittberner, as well as Anja Möbius, for their cooperation and help.
Thanks go to all mathematicians, living or dead, whose work I have cannibalized
freely – starting with Horst Herrlich, from whose bookAxiom of Choice(Springer,
Heidelberg 2006) I have taken this sentence.
Moreover, I thank all the students who have contributed over the years to improving
the course – especially Barbara Langfeld, who looked through a ﬁnal version of the
text. One of my ﬁrst students was Roland Kaschek, who became a professor in New
Zealand, and one of most recent was Xia Zhang, who is now a professor in China. I
thank all the colleagues who have used parts of my notes for their own courses and
lectures.
I thank Mati Kilp (Estonia) for his contributions to several parts of the book, and I
am grateful to Kolja Knauer for his comments, suggestions and contributions specially
to Chapter 13. I also thank Sayan Panma (Thailand) who contributed many results to
Chapters 11 and 12 while he was a PhD student at Oldenburg.
I thank Theresia Meyer for doing much of the typesetting of earlier versions, draw-
ing pictures and providing various other sorts of technical help.
Above all, I thank my wife Jane Richter for her many good ideas as a non-mathe-
matician, her encouragement and her patience with me during the intense periods of
work.
Oldenburg and Berlin, April 2011 Ulrich Knauer

Contents
Preface v
1 Directed and undirected graphs 1
1.1 Formaldescriptionofgraphs ...................... 1
1.2 Connectedness and equivalence relations ................ 4
1.3 Some special graphs.......................... 5
1.4 Homomorphisms ............................ 7
1.5 Half-, locally, quasi-strong and metric homomorphisms ........ 11
1.6 The factor graph, congruences, and the Homomorphism Theorem . . 14
Factor graphs.............................. 14
TheHomomorphismTheorem ..................... 15
1.7 The endomorphism type of a graph................... 18
1.8 Comments................................ 24
2 Graphs and matrices 26
2.1 Adjacency matrix . ........................... 26
Isomorphic graphs and the adjacency matrix . . ............ 28
Components and the adjacency matrix . ................ 29
Adjacency list.............................. 30
2.2 Incidencematrix ............................ 30
2.3 Distancesingraphs........................... 31
The adjacency matrix and paths .................... 32
The adjacency matrix, the distance matrix and circuits . ........ 33
2.4 Endomorphisms and commuting graphs ................ 34
2.5 The characteristic polynomial and eigenvalues . ............ 35
2.6 Circulantgraphs............................. 40
2.7 Eigenvaluesandthecombinatorialstructure .............. 43
Cospectral graphs . ........................... 43
Eigenvalues, diameter and regularity . . ................ 44
Automorphismsandeigenvalues .................... 45
2.8 Comments................................ 46
3 Categories and functors 48
3.1 Categories................................ 48
Categorieswithsetsandmappings,I.................. 49
Constructs, and small and large categories............... 49

xii Contents
Special objects and morphisms . .................... 50
Categorieswithsetsandmappings,II ................. 51
Categorieswithgraphs ......................... 51
Other categories . . ........................... 52
3.2 Products&Co. ............................. 53
Coproducts ............................... 53
Products................................. 55
Tensorproducts............................. 57
Categorieswithsetsandmappings,III................. 58
3.3 Functors................................. 58
Covariantandcontravariantfunctors.................. 59
Composition of functors . . . . .................... 59
Special functors – examples . . .................... 60
Morfunctors .............................. 60
Properties of functors.......................... 61
3.4 Comments................................ 63
4 Binary graph operations 64
4.1 Unions.................................. 64
Theunion................................ 64
Thejoin................................. 66
Theedgesum.............................. 67
4.2 Products................................. 70
The cross product . ........................... 71
The coamalgamated product . . .................... 72
The disjunction of graphs . . . . .................... 75
4.3 Tensor products and the product inEGra................ 75
The box product . . ........................... 76
The boxcross product.......................... 79
The complete product.......................... 79
Synopsis of the results . . . . . .................... 80
Product constructions as functors in one variable........... 80
4.4 Lexicographicproductsandthecorona................. 81
Lexicographicproducts......................... 81
Thecorona ............................... 82
4.5 Algebraic properties ........................... 83
4.6 Morconstructions............................ 85
Diamondproducts............................ 85
Leftinversesfortensorfunctors .................... 87
Powerproducts ............................. 88
Left inverses to product functors .................... 89
4.7 Comments................................ 90

Contents xiii
5 Line graph and other unary graph operations 91
5.1 Complements, opposite graphs and geometric duals . . ........ 91
5.2 Thelinegraph.............................. 92
Determinability ofGbyLG...................... 95
5.3 Spectra of line graphs.......................... 97
Whichgraphsarelinegraphs? ..................... 99
5.4 Thetotalgraph .............................101
5.5 Thetreegraph..............................102
5.6 Comments................................103
6 Graphs and vector spaces 104
6.1 Vertexspaceandedgespace ......................104
The boundary & Co...........................105
Matrix representation..........................106
6.2 Cycle spaces, bases & Co. . . . ....................107
Thecyclespace.............................107
Thecocyclespace............................109
Orthogonality..............................111
The boundary operator & Co. . . ....................112
6.3 Application: MacLane’s planarity criterion...............113
6.4 Homologyofgraphs ..........................116
Exact sequences of vector spaces ....................116
Chain complexes and homology groups of graphs...........117
6.5 Application: number of spanning trees . ................119
6.6 Application: electrical networks ....................123
6.7 Application: squared rectangles ....................128
6.8 Application: shortest (longest) paths . . ................132
6.9 Comments................................135
7 Graphs, groups and monoids 136
7.1 Groups of a graph . ...........................136
Edgegroup ...............................137
7.2 Asymmetricgraphsandrigidgraphs..................138
7.3 Cayleygraphs..............................144
7.4 Frucht-typeresults ...........................146
Frucht’s theorem and its generalization for monoids . . ........147
7.5 Graph-theoretic requirements . . ....................148
Smallest graphs for given groups ....................149
Additional properties of group-realizing graphs ............150
7.6 Transformation monoids and permutation groups...........154
7.7 Actionsongraphs............................156
Fixed-point-free actions on graphs...................156

xiv Contents
Transitive actions on graphs . . ....................157
Regular actions . . ...........................158
7.8 Comments................................160
8 The characteristic polynomial of graphs 161
8.1 Eigenvectors of symmetric matrices . . ................161
Eigenvalues and connectedness . ....................162
Regulargraphsandeigenvalues.....................163
8.2 Interpretation of the coefﬁcients of chapo.G/.............164
Interpretation of the coefﬁcients for undirected graphs . ........166
8.3 Spectra of trees . . ...........................168
Recursionformulafortrees.......................168
8.4 The spectral radius of undirected graphs ................169
Subgraphs . ...............................169
Upper bounds..............................170
Lower bounds..............................171
8.5 Spectral determinability . . . . . ....................172
Spectral uniqueness ofK
nandK p;q..................172
8.6 Eigenvalues and group actions . ....................174
Groups, orbits and eigenvalues . ....................174
8.7 Transitivegraphsandeigenvalues ...................176
Derogatorygraphs ...........................177
Graphs with Abelian groups . . ....................178
8.8 Comments................................180
9 Graphs and monoids 181
9.1 Semigroups ...............................181
9.2 End-regular bipartite graphs . . ....................185
Regular endomorphisms and retracts . . ................185
End-regular and End-orthodox connected bipartite graphs.......186
9.3 Locally strong endomorphisms of paths ................188
Undirected paths . ...........................188
Directed paths..............................191
Algebraic properties of LEnd . . ....................194
9.4 Wreath product of monoids over an act . ................197
9.5 Structure of the strong monoid . ....................200
The canonical strong decomposition ofG...............201
Decomposition of SEnd . . . . . ....................202
A generalized wreath product with a small category . . ........204
Cardinality of SEnd.G/.........................204
9.6 Some algebraic properties of SEnd...................205
Regularity and more forT
A.......................205

Contents xv
Regularity and more for SEnd.G/...................206
9.7 Comments................................207
10 Compositions, unretractivities and monoids 208
10.1Lexicographicproducts.........................208
10.2 Unretractivities and lexicographic products . . ............210
10.3 Monoids and lexicographic products . . ................214
10.4Theunionandthejoin .........................217
The sum of monoids..........................217
The sum of endomorphism monoids . . ................218
Unretractivities . . ...........................219
10.5 The box product and the cross product . ................221
Unretractivities . . ...........................222
The product of endomorphism monoids ................223
10.6Comments................................224
11 Cayley graphs of semigroups 225
11.1TheCayfunctor.............................225
Reﬂection and preservation of morphisms...............227
Does Cay produce strong homomorphisms? . . ............228
11.2 Products and equalizers . . . . . ....................229
Categorical products..........................229
Equalizers . ...............................231
Other product constructions . . . ....................232
11.3 Cayley graphs of right and left groups . ................234
11.4 Cayley graphs of strong semilattices of semigroups . . ........237
11.5 Application: strong semilattices of (right or left) groups ........240
11.6Comments................................244
12 Vertex transitive Cayley graphs 245
12.1Aut-vertextransitivity..........................245
12.2 Application to strong semilattices of right groups...........247
ColAut.S; C /-vertextransitivity ....................249
Aut.S; C /-vertextransitivity ......................250
12.3 Application to strong semilattices of left groups ............253
Application to strong semilattices of groups . . ............256
12.4 End
0
.S; C /-vertextransitiveCayleygraphs ..............256
12.5Comments................................260
13 Embeddings of Cayley graphs – genus of semigroups 261
13.1Thegenusofagroup ..........................261
13.2 Toroidal right groups..........................265

xvi Contents
13.3 The genus of.AR r/.........................270
Cayley graphs ofAR
4........................270
Constructions of Cayley graphs forAR
2andAR 3........270
13.4 Non-planar Clifford semigroups ....................275
13.5 Planar Clifford semigroups . . . ....................279
13.6Comments................................284
Bibliography 285
Index 301
Index of symbols 307

Chapter 1
Directed and undirected graphs
In this chapter we collect some important basic concepts. These concepts are essential
for all mathematical modeling based on graphs. The language and visual representa-
tions of graphs are such powerful tools that graph models can be encountered almost
everywhere in mathematics and informatics, as well as in many other ﬁelds.
The most obvious phenomena that can be modeled by graphs are binary relations.
Moreover, graphs and relations between objects in a formal sense can be considered
the same. The concepts of graph theory also play a key role in the language of category
theory, where we consider objects and morphisms.
It is not necessary to read this chapter ﬁrst. A reader who is already familiar with
the basic notions may just refer back to this chapter as needed for a review of the
notation and concepts.
1.1 Formal description of graphs
We shall use the word “graph” to refer to both directed and undirected graphs. Only
when discussing concepts or results that are speciﬁc to one of the two types of graph
we will use the corresponding adjective explicitly. An edge of a graph will be denoted
by.x; y/; this notation will also be used for directed graphs, whereas an edge in the
particular case of undirected graphs will be written as¹x;yº.
Deﬁnition 1.1.1.Adirected graphordigraphis a tripleGD.V;E;p/whereVand
Eare sets and
pWE!V
2
is a mapping. We callVthe set ofverticesorpointsandEthe set ofedgesorarcsof
the graph, and we will sometimes write these sets asV.G/andE.G/. The mapping
pis called theincidence mapping.
The mappingpdeﬁnes two more mappingso; tWE!Vby.o.e/; t.e//WDp.e/;
these are also called incidence mappings. We callo.e/theoriginorsourceandt.e/
thetailorendofe.
Aspdeﬁnes the mappingsoandt, these in turn deﬁnepbyp.e/WD.o.e/; t.e//.
We will mostly be using the ﬁrst of the two alternatives
GD.V;E;p/orGD.V;E;o;t/:
We say that the vertexvand the edgeeareincidentifvis the source or the tail
ofe. The edgeseande
0
are said to beincidentif they have a common vertex.

2 Chapter 1 Directed and undirected graphs
Anundirected graphis a tripleGD.V;E;p/such that
pWE!¹VVj1jVj2º:
An edgeewitho.e/Dt.e/is called aloop.AgraphGis said to belooplessif it
has no loops.
LetGD.V;E;o;t/be a directed graph, letebe an edge, and letuDo.e/and
vDt.e/; then we also writeeWu!v. The vertices of graphs are drawn as points
or circles; directed edges are arrows from one point to another, and undirected edges
are lines, or sometimes two-sided arrows, joining two points. The name of the vertex
or edge may be written in the circle or close to the point or edge.
Deﬁnition 1.1.2.LetGD.V;E;p/be a graph. Ifpis injective, we callGasim-
ple graph(or agraph without multiple edges). Ifpis not injective, we callGa
multigraphormultiple graph; sometimes the termpseudographis used.
IfGD.V;E;p/is a simple graph, we can considerEas a subset ofV
2
, identify-
ingp.E/withE. We then writeGD.V; E/orGD.V
G;EG/, and for the edgee
withp.e/D.x; y/we write.x; y/.
Simple graphs can now be deﬁned as follows: asimple directed graphis a pair
GD.V; E/withEV
2
DVV. Then we again callVthe set ofverticesandE
the set ofedges.
Asimple undirected graphis a simple directed graphGD.V; E/such that
.x; y/2E,.y; x/2E:
The edge.x; y/may also be written as¹x;yºorxy.
MappingswWE!WorwWV!Ware calledweight functions.HereWis
any set, called theset of weights,andw.x/is called theweightof the edgexor of the
vertexx.
Deﬁnition 1.1.3.Apathafromxtoyor anx; ypathin a graphGis a sequence
aD.e
1;e2;:::;en/of edges witho.e 1/Dx,t.e n/Dyandt.e i1/Do.e i/for
iD2;:::;n. We writeaWx!yand callxthestart (origin, source)andythe
end (tail, sink)of the patha. The sequencex
0;:::;xnis called thetraceof the path
a.Theset¹x
0;:::;xnºof all vertices of the trace is called thesupport of the patha,
denoted by suppa.
A path is said to besimpleif every vertex appears at most once on the path. A
path is said to beclosed, or is called acycle, if the start and end of the path coincide.
A simple closed path, i.e. a simple cycle, is called acircuit.Thewords(simple)
semipath, semicycleorsemicircuitwill be used if, in the sequence of edges, the tail
or origin of each edge equals the origin or tail of the next edge. This means that at
least two consecutive edges have opposite directions. The notions of trace and support

Section 1.1 Formal description of graphs 3
remain unchanged. In a simple graph, every (semi)path is uniquely determined by its
trace. We can describe a path also by its verticesx
0;:::;xnwhere.x 0;x1/,:::,
.x
n1;xn/are edges of the path. For undirected graphs, the notions of path and
semipath are identical.
For the sake of completeness we also mention the following deﬁnition: thetrivial
x; xpathis the path consisting only of the vertexx. It is also called alazy path.
The reader should be aware that, in the literature, the words “cycle” and “circuit”
are often used in different ways by different authors.
Lemma 1.1.4.Forx;y2G, everyx;ypath contains a simplex;ypath. Every
cycle inGis the union of circuits.
Proof.Takex;y2G. Start on anx;ypath fromxand proceed until one vertexz
is met for the second time. If this does not happen, we already have a simple path;
otherwise, we have also traversed a circuit. Remove this circuit, together with all its
vertices butz, from the path. Continuing this procedure yields a simplex;ypath. If
we start with a cycle, we remove one edgeeD.y; x/, and this gives anx;ypath.
Now collect the circuits as before. At the end we have a simplex;ypath, which
together withegives the last circuit.
Deﬁnition 1.1.5.LetGD.V; E/, and letaD.e 1;:::;er/be a path withe i2E.
Then`.a/WDris called thelengthofa.
We denote byF.x;y/the set of allx;ypaths inG.Thend.x;y/WDmin¹`.a/j
a2F.x;y/ºis called thedistancefromxtoy.
We call diam.G/WDmax
x;y2G d.x;y/thediameterofG. The length of a shortest
cycle ofGis called thegirthofG. In German the ﬁgurative wordTaillenweite,
meaning circumference of the waist, is used.
Remark 1.1.6.In connected, symmetric graphs the distancedWVV!R
C
0
is
a metric, if we setd.x;x/D0for allx2V.Inthisway,.V; d/becomes a metric
space. If¹`.a/ja2F.x;y/ºD;,thend.x;y/is not deﬁned. Often one sets
d.x;y/D1in this case.
Deﬁnition 1.1.7.For a vertexxof a graphG,theoutsetofxis the set
out.x/WDout
G.x/WD ¹e2Ejo.e/Dxº:
The elements of
N
C
.x/WDN
C
G
.x/WD ¹t.e/je2out G.x/º
are called thesuccessorsofxinG.Theoutdegreeof a vertexxis the number of
successors ofx;thatis,

d.x/Doutdeg.x/WD jout.x/j:

4 Chapter 1 Directed and undirected graphs
Deﬁnition 1.1.8.The graphG
op
WD.V;E;t;o/is called theopposite graphtoG.
Theinsetof a vertexxis the outset ofxin the opposite graphG
op
,so
in.x/Din
G.x/WDout G
op.x/D¹e2Ejt.e/Dxº:
The elements of
N

.x/WDN

G
.x/WDN
C
G
op.x/WD ¹o.e/je2in G.x/º
are calledpredecessorsofxinG.Theindegreeof a vertexxis the number of
predecessors ofx;thatis,
!
d.x/Dindeg.x/WD jin.x/j:
A vertex which is a successor or a predecessor of the vertexxis said to beadjacent
tox.
Deﬁnition 1.1.9.In an undirected graphG, a predecessor of a vertexxis at the
same time a successor ofx. Therefore, in this case, in.x/Dout.x/andN.x/WD
N
C
.x/DN

.x/. We call the elements ofN.x/theneighborsofx. Similarly,
indeg.x/Doutdeg.x/. The common valued
G.x/Dd.x/Ddeg.x/is called the
degreeofxinG.
An undirected graph is said to beregularord-regularif all of its vertices have
degreed.
1.2 Connectedness and equivalence relations
Here we make precise some very natural concepts, in particular, how to reach certain
points from other points.
Deﬁnition 1.2.1.A directed graphGis said to be:
weakly connectedif for allx;y2Vthere exists a semipath fromxtoy;
one-sided connectedif for allx;y2Vthere exists a path fromxtoyor from
ytox;
strongly connectedif for allx;y2Vthere exists a path fromxtoyand from
ytox.
For undirected graphs, all of the above three concepts coincide. We then simply say
that the graph isconnected; we shall also use this word as a common name for all
three concepts.
IfGsatisﬁes none of the above three conditions, it is said to beunconnectedor
disconnected.

Section 1.3 Some special graphs 5
Example 1.2.2.The following three graphs illustrate the three properties above, in
the order given.

Deﬁnition 1.2.3.A connected graph is said to ben-vertex connectedif at leastn
vertices must be removed to obtain an unconnected graph. Analogously, one can
deﬁnen-edge connectedgraphs.
Remark 1.2.4.Abinary relationon a setXis usually deﬁned as a subset of the
Cartesian productXX. This often bothers beginners, since it seems too simple a
deﬁnition to cover all the complicated relations in the real world that one might wish
to model. It is immediately clear, however, that every binary relation is a directed
graph and vice versa. This is one reason that much of the literature on binary relations
is actually about graphs. Arbitrary relations on a set can similarly be described by
multigraphs.
Anequivalence relationon a setX, i.e. a reﬂexive, symmetric and transitive binary
relation in this setting, corresponds to a disjoint union of various graphs with loops
at every vertex (reﬂexivity) which are undirected (symmetry), and such that any two
vertices in each of the disjoint graphs are adjacent (transitivity). Note that the above-
mentioned disjoint union is due to the fact that an equivalence relation on a setX
provides a partition of the setXinto disjoint subsets and vice versa.
1.3 Some special graphs
We now deﬁne some standard graphs. These come up everywhere, in virtually any
discussion about graphs, so will serve as useful examples and counterexamples.
Deﬁnition 1.3.1.In thecomplete graphK
.l/
n
withnvertices andlloops, where0
ln, any two vertices are adjacent andlof the vertices have a loop.
Thetotally disconnectedordiscrete graph
K
.l/
n
withnvertices andlloops has no
edges between distinct vertices and has loops atlvertices. IflD0, we writeK
nor
Kn.
A simple, undirected path withnedges is denoted byP
n.
An undirected circuit withnedges is denoted byC
n.
Anr-partite graphadmits a partition of the vertex setVintordisjoint subsets
V
1;:::;Vrsuch that no two vertices in one subset are adjacent.
Anr-partite graph is said to becompleter-partiteif all pairs of vertices from
different subsets are adjacent. The complete bipartite graph withjV
1jDmandjV 2jD
nis denoted byK
m;n; similarly for completer-partite graphs.

6 Chapter 1 Directed and undirected graphs
Example 1.3.2(Some special graphs).
K
1: K 2: K 3: K 4:

K2;3:

K
.2/
4
:

K4:

K
.2/
4
:

P2:

C3DK3,C 4DK2;2:

Deﬁnition 1.3.3.A graph without (semi)circuits is called aforest. A connected forest
is called atreeofG. A connected graphG
0
with the same vertex set asGis called a
spanning treeif it is a tree. IfGis not connected, the union of spanning trees for the
components ofGis called aspanning forest.
Theorem 1.3.4.LetGbe a graph withnvertices. The following statements are
equivalent:
(i)Gis a tree.
(ii)Gcontains no semicircuits and hasn1edges.
(iii)Gis weakly connected and hasn1edges.
(iv)Any two vertices ofGare connected by a semipath.
(v)Adding any one edge produces exactly one semicircuit.
Proof.We describe brieﬂy the idea of the proof. Starting from some tree, i.e. state-
ment (i), we verify (ii); then show the converse, that if (ii) does not hold then we
cannot have a tree, and so on.
Theorem 1.3.5.A graph is bipartite if and only if it has no semicircuits with an odd
number of edges.

Section 1.4 Homomorphisms 7
Proof.For “)”, letVDV 1
S
V
2. Since edges exist only betweenV 1andV 2, all
circuits must have an even number of edges.
For “(”, letGbe connected and takex2V.TakeV
1to be the set of all vertices
which can be reached fromxalong paths using an odd number of edges. SetV
2WD
VnV
1.IfGis not connected, proceed in the same way with its connected parts.
Isolated vertices can be assigned arbitrarily.
We recall the following deﬁnition: a pair.P;/,wherePis a set with a reﬂexive,
antisymmetric, transitive binary relation, is called apartially ordered setor aposet.
We writex<yifxyandx¤y. We say thatycoversx, writtenxy,ifx<y
and ifxz<yimpliesxDz. See also Remark 1.2.4.
Proposition 1.3.6.Every ﬁnite partially ordered set.P;/deﬁnes a simple directed
graphH
Pwithout cycles with vertex setPand edge set¹.x; y/jxyº,theso-
called Hasse diagram of.P;/, and conversely. Deﬁning the edge set by¹.y; x/j
xyºgives a Hasse diagram where arcs are directed “down”.
Proof.A simple, directed graphHwithout cycles describesPcompletely, sincex
yif and only if eitherxDyor there exists anx;ypath inHwhose edges.x
i;xiC1/
are interpreted asx
ixiC1.
For the converse we use analogous arguments.
Deﬁnition 1.3.7.Arooted treeis a triple.T;;r/such that:
.T;/is a partially ordered set;
HTis a tree; and
r2Tis an element, theroot of the tree,wherexrfor allx2T.
Amarked rooted treeis a quadruple.T;;r;/such that.T;;r/is a rooted tree
andWT!M, withMbeing a set, is a mapping (weight function), which in this
context is called themarking function. We call.x/amarkingofx.
1.4 Homomorphisms
In mathematics, as in the real world, mappings produce images. In such images,
certain aspects of the original may be suppressed, so that the image is in general
simpler than the original. But some of the structures of the original, those which
we want to study, should be preserved. Structure-preserving mappings are usually
called homomorphisms. For graphs it turns out that preservation of different levels of
structure or different intensities of preservation quite naturally lead to different types
of homomorphism.
First, we give a very general deﬁnition of homomorphisms. We will then intro-
duce the so-called covering, which has some importance in the ﬁeld of informatics.

8 Chapter 1 Directed and undirected graphs
The general deﬁnition will then be specialized in various ways, and later we will use
almost exclusively these variants. A reader who is not especially interested in the
general aspects of homomorphisms may wish to start with Deﬁnition 1.4.3.
Deﬁnition 1.4.1.LetG
1D.V1;E1;o1;t1/andG 2D.V2;E2;o2;t2/be two di-
rected graphs. Agraph homomorphismWG
1!G 2is a pairD. V;E/of
mappings

VWV1!V2
EWE1!E 2
such thato 2.E.e//D V.o1.e//andt 2.E.e//D V.t1.e//for alle2E 1.
IfWG
1!G 2is a graph homomorphism andvis a vertex ofG 1,then

E.outG1
.v//out G2
.V.v//and E.inG1
.v//in G2
.V.v//:
Deﬁnition 1.4.2.If
Ej
outG
1.v/is bijective for allv2V, we callacoveringofG 2.
If
Ej
outG
1.v/is only injective for allv2V, then it is called aprecovering.
For simple directed or undirected graphs, we will mostly be working with the fol-
lowing formulations and concepts rather than the preceding two deﬁnitions.
The main idea is that homomorphisms have to preserve edges. If, in the following,
we replace “homo” by “ega”, we have the possibility of identifying adjacent vertices
as well. This could also be be achieved with usual homomorphisms if we consider
graphs that have a loop at every vertex.
Deﬁnition 1.4.3.LetGD.V; E/andG
0
D.V
0
;E
0
/be two graphs. A mapping
fWV!V
0
is called a:
graph homomorphismif.x; y/2E).f .x/; f .y//2E
0
;
graph egamorphism (weak homomorphism)if.x; y/2Eandf.x/¤f.y/)
.f .x/; f .y//2E
0
;
graph comorphism (continuous graph mapping)if.f .x/; f .y//2E
0
)
.x; y/2E;
strong graph homomorphismif.x; y/2E,.f .x/; f .y//2E
0
;
strong graph egamorphismif.x; y/2Eandf.x/¤f.y/,.f .x/; f .y//2E
0
;
graph isomorphismiffis a strong graph homomorphism and bijective or,
equivalently, iffandf
1
are graph homomorphisms.
WhenGDG
0
, we use the preﬁxes “endo”, “auto” instead of “homo”, “iso” etc.
We note that the term “continuous graph mapping” is borrowed from topology; there
continuous mappings reﬂect open sets, whereas here they reﬂect edges.

Section 1.4 Homomorphisms 9
Remark 1.4.4.Note that, in contrast to algebraic structures, bijective graph homo-
morphisms are not necessarily graph isomorphisms. This can be seen from Exam-
ple 1.4.9; there the non-strong subgraph can be mapped bijectively onto the graphG
without being isomorphic to it.
Remark 1.4.5.Note that forf
02EHom.G; G
0
/, which identiﬁes exactly two adja-
cent vertices, the graphf
0.G/is also called anelementary contractionofG.There-
sult of a series of elementary contractionsf
n.fn1.:::.f0.G//::://is usually called
acontractionofG. This terminology is used mainly for the characterization of planar
graphs (see Chapter 13).
Remark 1.4.6.Denote by Hom.G; G
0
/,Com.G; G
0
/,EHom.G; G
0
/, SHom.G; G
0
/,
SEHom.G; G
0
/and Iso.G; G
0
/the homomorphism sets.
Analogously, let End.G/, EEnd.G/,Cnd.G/,SEnd.G/, SEEnd.G/and Aut.G/
denote the respective sets whenGDG
0
. These form monoids.
Indeed, End.G/and SEnd.G/, as well as EEnd.G/and SEEnd.G/, are monoids,
i.e. sets with an associative multiplication (the composition of mappings) and an iden-
tity element (the identical mapping). Clearly, End.G/is closed. Also, SEnd.G/is
closed, since forf; g2SEnd.G/we get
.fg.x/; fg.y//2E
fstrong
(HHH).g.x/; g.y//2E
gstrong
(HH).x; y/2E:
The rest is clear.
Proposition 1.4.7.LetGandG
0
be graphs andfWG!G
0
a graph isomorphism.
Forx2G, we haveindeg.x/Dindeg.f .x//andoutdeg.x/Doutdeg.f .x//.
Proof.We prove the statement for undirected graphs.
Asfis injective, we getjN
G.x/jDjf.N G.x//j.
Asfis a homomorphism, we getf.N
G.x//N G
0.f .x//,i.e.jf.N G.x//j
jN
G
0.f .x//j.
Asfis surjective, we haveN
G
0.f .x//f.G/; and, sincefis strong, we get
jN
G
0.f .x//jjN G.x/j.
Putting the above together, using the statements consecutively, we obtainjN
G.x/jD
jN
G
0.f .x//j.
Now we use deg.x/DjN
G.x/jand deg.f .x//DjN G
0.f .x//jto get the result.
Subgraphs
The different sorts of homomorphisms lead to different sorts of subgraphs. First, let
us explicitly deﬁne subgraphs and strong subgraphs.

10 Chapter 1 Directed and undirected graphs
Deﬁnition 1.4.8.LetGD.V; E/.AgraphG
0
D.V
0
;E
0
/is called asubgraph(or
partial subgraph)ofGif there exists an injective graph homomorphismfWV
0
!V.
AgraphG
0
is called astrong subgraph(orinduced subgraphorvertex induced
subgraph) if there exists an injective strong graph homomorphismfWV
0
!V.
Example 1.4.9(Subgraphs).

is a not strong subgraph while

is a strong subgraph ofG:

Remark 1.4.10.A strong subgraph in general has fewer vertices than the original
graph, but all edges of the original graph between these vertices are contained in the
strong subgraph.
A subgraph in general contains fewer vertices and fewer edges than the original
graph.
(Semi)paths, (semi)cycles and (semi)circuits are all subgraphs.
Deﬁnition 1.4.11.Astrong,one-sidedorweak componentof a graph is, respec-
tively, a maximal strongly, one-sided or weakly connected subgraph.
A (strong) component is also called acliqueofG. The number of vertices!.G/of
the largest clique ofGis called theclique numberofG.
See Example 1.2.2 for comparison.
The “edge dual” concept to a clique is a maximal independent subset ofV.
Deﬁnition 1.4.12.Two verticesx;y2Vare calledindependent verticesif.x; y/…
Eand.y; x/…E.Thevertex independence numberis deﬁned as
ˇ
0.G/WDmax¹jUjWUV;independentº:
Analogously, two non-incident edges are calledindependent edges, and we can
deﬁne theedge independence numberˇ
1.G/.
The elements of an independent edge set ofGare also called1-factorsofG;a
maximal independent edge set ofGis called amatchingofG.

Section 1.5 Half-, locally, quasi-strong and metric homomorphisms 11
1.5 Half-, locally, quasi-strong and metric homomorphisms
In addition to the usual homomorphisms, we introduce the following four sorts of
homomorphisms. As always, homomorphisms are used to investigate the structure of
objects. The large number of different homomorphisms of graphs shows how rich and
variable the structure of a graph can be. In Section 1.8 we summarize which of these
homomorphisms have appeared where and under which names; we also suggest how
they might be used in modeling.
The motivation for these other homomorphisms comes from the concept of strong
homomorphisms or, more precisely, the notion of comorphism, i.e. the continuous
mapping. A continuous mapping “reﬂects” edges of graphs. The following types
of homomorphism reduce the intensity of reﬂection. In other words, an ordinary
homomorphismfWG!G
0
does not reﬂect edges at all. This means it could happen
that.f .x/; f .y//is an edge inG
0
even though.x; y/is not an edge inG, and there
may not even exist any preimage off.x/which is adjacent to any preimage off.y/
inG. The following three concepts “improve” this situation step by step.
From the deﬁnitions it will become clear that there exist intermediate steps that
would reﬁne the degree of reﬂection.
Deﬁnition 1.5.1.LetGD.V; E/andG
0
D.V
0
;E
0
/be graphs, and letf2
Hom.G; G
0
/.Forx;y2V,set
XWDf
1
.f .x//;
YWDf
1
.f .y//:
Let.f .x/; f .y//2E
0
.Thenfis said to be:
half-strongif there existsQx2XandQy2Ysuch that.Qx;Qy/2E;
locally strongif
²
8x2X;9y
x2Ysuch that.x; y x/2Eand
8y2Y;9x
y2Xsuch that.x y;y/2EI
quasi-strongif
²
9Qx
02Xsuch that8Qy2Y; .Qx 0;Qy/2Eand
9Qy
02Ysuch that8Qx2X; .Qx;Qy 0/2E:
We callQx
0andQy 0central verticesor, in the directed case, thecentral source
andcentral sinkinXand inYwith respect to.f .x/; f .y//.
Remark 1.5.2.With the obvious notation, one has
Hom.G; G
0
/HHom.G; G
0
/LHom.G; G
0
/QHom.G; G
0
/
SHom.G; G
0
/Iso.G; G
0
/;
End.G/HEnd.G/LEnd.G/QEnd.G/
SEnd.G/Aut.G/?id
Gº:

12 Chapter 1 Directed and undirected graphs
Note that apart from SEnd.G/,Aut.G/and¹id Gº, the other subsets of End.G/are,
in general, not submonoids of End.G/. We will talk about thegroupand thestrong
monoidof a graph, and about thequasi-strong monoid,locally strong monoidand
half-strong monoidof a graph if these really are monoids.
Example 1.5.3(Different homomorphisms). We give three of the four examples for
undirected graphs. The example for the half-strong homomorphism in the directed
case shows that the other concepts can also be transferred to directed graphs.
f
f
f.y/
f.x/
Qy
Qx
Y
X
G half-strong
f
f
f.y/
f.x/
Y
X
G locally strong
Qx0
Qy0
f
f
f.y/
f.x/
Y
X
G quasi-strong
f
f
f.y/
f.x/
Y
X
Gstrong
From the deﬁnitions we immediately obtain the following theorem. To get an idea
of the proof, one can refer to the graphs in Example 1.5.3.
Theorem 1.5.4.LetG¤K
1be a bipartite graph withVDV 1
S
V
2.Let.x 1;x2/
be an edge withx
12V1andx 22V2. We deﬁne an endomorphismrofGby
r.V
1/D¹x 1ºandr.V 2/D¹x 2º. Obviously,r2HEnd.G/. Moreover, the following
hold:
r2LEnd.G/if and only ifGhas no isolated vertices;
r2QEnd.G/if and only ifV 1has a central vertexex 0withN.ex 0/DV 2and
correspondingly forV
2;
r2SEnd.G/if and only ifGis complete bipartite.

Section 1.5 Half-, locally, quasi-strong and metric homomorphisms 13
Proposition 1.5.5.A non-injective endomorphismfofGis strong if and only if for
allx2Vwithf.x/Df.x
0
/one hasN G.x/DN G.x
0
/.
Note that for adjacent verticesxandx
0
, this is possible only if both have loops.
Proof.Necessity is clear from the deﬁnition. Now suppose thatN
G.x/DN G.x
0
/
forx;x
0
2V.G/. Constructfby settingf.x/Dx
0
andf.y/Dyfor ally¤x;x
0
.
It is clear thatf2SEnd.G/.
Corollary 1.5.6.IfAut.G/¤SEnd.G/,thenjSEnd.G/nAut.G/jcontains at least
two idempotents.
Deﬁnition 1.5.7.A homomorphismffromGtoG
0
is said to bemetricif for any
verticesx;y2V.G/there existx
0
2f
1
f.x/andy
0
2f
1
f.y/such that
d.f .x/; f .y//Dd.x
0
;y
0
/. Denote by MEnd.G/the set of metric endomorphisms
ofGandbyIdpt.G/the set ofidempotentendomorphisms, i.e.f2End.G/with
f
2
Df,ofG.
As usual we make the following deﬁnition.
Deﬁnition 1.5.8.A homomorphismffromGtof.G/His called aretractionif
there exists an injective homomorphismgfromf.G/ftoGsuch thatfgDid
f.G/.
In this casef.G/is called aretractofG, and thenGis called acoretractoff.G/
whilegis called acoretraction.
IfHis an unretractive retract ofG,i.e.ifEnd.H/DAut.H/,thenHis also called
acoreofG.
Remark 1.5.9.One has
Idpt.G/;LEnd.G/MEnd.G/HEnd.G/:
Example 1.5.10(HEnd, LEnd, QEnd are not monoids). The sets HEnd, LEnd, QEnd
are not closed with respect to composition of mappings. To see this, consider the
following graphG
together with the mappingsfD

12345
34545

andgD

12345
12325

.Nowf2
QEnd.G/andg2HEnd.G/butf
2
2HEnd.G/nLEnd.G/andgıf2End.G/n
HEnd.G/. These properties are not changed if we add another vertex 0 to the graph
which we make adjacent to every other vertex. The graph is then connected but no
longer bipartite.
Question.Do Idpt and MEnd always form monoids? Can you describe graphs where
this is the case?

14 Chapter 1 Directed and undirected graphs
1.6 The factor graph, congruences, and the
Homomorphism Theorem
The study of factor graphs by graph congruences turns out to be fundamental for
the general investigation of homomorphisms. The connection to arbitrary homomor-
phisms is established through the canonical epimorphisms, and this leads to the Ho-
momorphism Theorem for graphs. We formulate the theorem only for ordinary graph
homomorphisms.
Factor graphs
Deﬁnition 1.6.1.Let%VVbe an equivalence relation on the vertex setVof
agraphGD.V; E/, and denote byx
%the equivalence class ofx2Ewith respect
to%.ThenG
%D.V%;E%/is called thefactor graphofGwith respect to%,where
V
%DV
ı
%and.x %;y%/2E %if there existx
0
2x%andy
0
2y%with.x
0
;y
0
/2E,
where%is called agraph congruence.
Example 1.6.2(Congruence classes, factor graphs). We exhibit some graphs together
with congruence classes (encircled vertices) and the corresponding factor graphs:
G G %

Section 1.6 The factor graph, congruences, and the Homomorphism Theorem15
Remark 1.6.3.By the deﬁnition ofG %, the canonical epimorphism

%WG!G %
x7 !x %
(which is always surjective) is a half-strong graph homomorphism.
Note that, in general, a graph congruence%is just an equivalence relation. If we
have a graphGD.V; E/and a congruence%VVsuch that there existx;y2V
with.x; y/2Eandx%y,then.x
%;x%/2E %,i.e.G %has loops.
If we want to use only loopless graphs, then
%WG!G %is a graph homomor-
phism only if
x%y).x; y/…E:
Therefore we make the following deﬁnition.
Deﬁnition 1.6.4.A(loop-free) graph congruence%is an equivalence relation with
the additional property thatx%y).x; y/…E.
Deﬁnition 1.6.5.LetG
%be the factor graph ofGwith respect to%. If the canonical
mapping
%WG!G %is a strong (respectively quasi-strong, locally strong or metric)
graph homomorphism, then the graph congruence%is called astrong (respectively
quasi-strong, locally strong or metric) graph congruence.
Example 1.6.6(Connectedness relations). OnGD.V; E/, withx;y2V, consider
the following relations:
x%
1y,there exists anx;ypath and ay;xpath orxDy;
x%
2y,there exists anx;ysemipath orxDy.
x%
3y,there exists anx;ypath or ay;xpath.
The relation%
1is an equivalence relation; the factor graphG %1
is called aconden-
sationofG.
The relation%
2is an equivalence relation; the factor graphG %2
consists only of
isolated vertices with loops.
The relation%
3is not transitive and therefore not an equivalence relation.
The Homomorphism Theorem
For convenience we start with the so-called Mapping Theorem, i.e. the Homomor-
phism Theorem for sets, preceded by the usual result on mapping-induced congruence
relations. Then, as for sets, we formulate the Homomorphism Theorem for graphs.

16 Chapter 1 Directed and undirected graphs
Proposition 1.6.7.LetGandHbe sets, and letfWG!Hbe a mapping. Using
fwe obtain an equivalence relation onG, the so-calledinduced congruence,ifwe
deﬁne, forx;y2G,
x%
fy,f.x/Df.y/:
Moreover, by setting
%f
.x/Dx %f
forx2G, we get a surjective mapping onto the
factor setG
%f
DG=%
f.Herex %f
denotes the equivalence class ofxwith respect to
%
fandG=%
fthe set of all these equivalence classes.
Proof.It is straightforward to check that%
fis reﬂexive, symmetric and transitive, i.e.
it is an equivalence relation onG. Surjectivity of
%f
follows from the deﬁnition of
the factor set.
Proposition 1.6.8.LetGandHbe graphs, and letfWG!Hbe a graph homo-
morphism. Usingfwe obtain a graph congruence by deﬁning, forx;y2V.G/,
x%
fy,f.x/Df.y/:
Moreover, by setting
%f
.x/Dx %f
forx2G, we get a surjective graph homomor-
phism onto the factor graphG
%f
DG=%
f.Herex %f
denotes the congruence class of
xwith respect to%
fandG %f
the factor graph formed by these congruence classes.
Proof.As for sets we know that%
fis an equivalence relation and %f
is a surjective
mapping by Proposition 1.6.7. Now use Remark 1.6.3.
Proposition 1.6.9(The Homomorphism Theorem for sets).For every mappingfW
G!Hfrom a setGtoasetH, there exists exactly one injective mappingfW
G
%f
!H, with
f.x%f
/Df.x/forx2G, such that the following diagram is
commutative, i.e.fDfı %f
:
G
%f
GH

%f
f
f
Moreover, the following statements hold:
(a)Iffis surjective, thenfis surjective.
(b)If we replace%
fby an equivalence relation%%
f,then
fWG %!His
deﬁned in the same way, but is injective only if%D%
f.

Section 1.6 The factor graph, congruences, and the Homomorphism Theorem17
Proof.Deﬁnefas indicated. We shall show thatfis well deﬁned. Suppose that
x
%f
Dx
0
%
f
inG%f
;thenx%
fx
0
and thus
f.x%f
/Df.x/Df.x
0
/Df.x
0
%
f
/.
It is clear that
fmakes the diagram commutative and is the uniquely determined
mapping with these properties. Indeed, if a mappingf
0
has the same properties, then
f
0
.x%f
/Df
0
%f
.x/Df.x/Df%f
.x/Df.x%f
/for allx %f
2G%f
.
It is also clear that the two additional properties are valid. In particular, the inclusion
%%
fensures that
fis well deﬁned also in this case.
Theorem 1.6.10(The Homomorphism Theorem for graphs).For every graph ho-
momorphismfWG!H, there exists exactly one injective graph homomorphism
fWG %f
!H, withf.x%f
/Df.x/forx2G, such that the following diagram is
commutative, i.e.fDfı %f
:
G
%f
GH

%f
f
f
Moreover, the following statements hold:
(a)Iffis surjective, thenfis surjective.
(b)If we replace%
fby a graph congruence%%
f,then
fWG %!His deﬁned
in the same way, but is injective only if%D%
f.
Proof.Deﬁne
fas indicated, just as we did for sets in Proposition 1.6.9. Thenfis
well deﬁned, is unique and makes the diagram commutative.
We only have to show that
%f
and
fare graph homomorphisms. For

%f
this comes from Proposition 1.6.8. Take.x %f
;y%f
/2E.G %f
/and consider
.
f.x%f
/;f.y%f
//D.f .x/; f .y//. Now there exists a preimage.x
0
;y
0
/2E.G/of
.x
%f
;y%f
/2E.G %f
/, which implies.f .x/; f .y//2E.H/.
The two additional properties are the same as for sets, so nothing further needs to
be proved.
Remark 1.6.11.In category-theoretical language, the essence of the Homomorphism
Theorem is that every homomorphism has anepi-mono factorizationin the given
category. Note that in the graph categories considered, epimorphisms (epis) are sur-
jective and monomorphism (monos) are injective. The monomorphism is called an
embeddingof the factor graph into the image graph.

18 Chapter 1 Directed and undirected graphs
Corollary 1.6.12.Surjective endomorphisms and injective endomorphisms of a ﬁnite
graph (set) are already automorphisms.
Example 1.6.13.We consider again the homomorphismffrom Example 1.5.10.
Here the congruence classes are¹1º;¹2;4ºand¹3; 5º,so
%f
maps every vertex to
its congruence class, and
fis the embedding which takes1 %f
to 3,2 %f
to4and3 %f
to 5. The result of this procedure can be visualized in a diagram as follows:
Application 1.6.14.As an application, we observe that the Homomorphism Theorem
can be used to determine all homomorphisms fromGtoHas follows. We ﬁrst
determine all congruences onG, giving all possible natural surjections. Then, for
each congruence relation%which is given by its congruence classes, i.e. for every

%, we determine all possible embeddings ofG %
intoH. Each of these embeddings
corresponds to somef, all of which different but induce the same congruence.
In the example considered, we haveGDHand obtain all embeddings as follows.
The class¹1ºcan be mapped onto any vertex ofG, and after that the classes¹2;4ºand
¹3; 5ºforming an edge inG
%
can be mapped onto every edge ofGwhich does not
contain the image of¹1ºin the actual embedding. In particular, if we map¹1ºonto
1 we have six possible embeddings, and they all give quasi-strong endomorphisms.
If we map¹1ºonto 3 or 4, we have four possible embeddings in each case, two of
which give quasi-strong and the other two ordinary endomorphisms. If we map¹1º
onto 2 or 5 ,we have two possible embeddings, which in each case give ordinary
endomorphisms. So, overall, this congruence relation gives ten quasi-strong and eight
ordinary endomorphisms.
The same method for groups is formulated in Project 9.1.8.
1.7 The endomorphism type of a graph
For a more systematic treatment of different endomorphisms we deﬁne the endomor-
phism spectrum and the endomorphism type of a graph.
Deﬁnition 1.7.1.For the graphXconsider the following sequence from Remark 1.5.2
(brackets aroundGare omitted for simplicity):
EndGHEndGLEndGQEndGSEndGAutG:
With this sequence we associate the sequence of respective cardinalities,
EndospecGD.jEndGj;jHEndGj;jLEndGj;jQEndGj;jSEndGj;jAutGj/;

Section 1.7 The endomorphism type of a graph 19
and we call this 6-tuple theendospectrumorendomorphism spectrumofG.Next,
associate with the above sequence a 5-tuple.s
1;s2;s3;s4;s5/with
s
i2¹0; 1ºforiD1;:::;5;
wheres
iD1stands for¤ands iD0stands forD;
such thats
1D1means thatjEndGj¤jHEndGj,s 2D0means thatjHEndGjD
jLEndGj, etc. We use decadic coding and call the integer
P
5
iD1
si2
i1
theendotype
orendomorphism typeofGand denote it byendotypeG.
If EndGDAutG, we call the graphGunretractiveor E-Aunretractive;if
EndGD1, we call the graphrigid;andifAutGD1, we call the graphasym-
metric. More generally, ifXGDX
0
GforX; X
0
2¹End;HEnd;LEnd;QEnd;Autº,
we call the graphX-X
0
unretractive.
In principle there are 32 possibilities, i.e. endotype 0 up to endotype 31.
We will now prove that graphs of endotypes 1 and 17 do not exist.
Proposition 1.7.2.LetGbe a ﬁnite graph such thatEndG¤HEndG.Then
HEndG¤SEndG.
Proof.Takef2EndGnHEndG. Then there exists.f .x/; f .x
0
//2E.G/but
for all
x;x
0
withf.x/Df.x/andf.x
0
/Df.x
0
/one has.x;x
0
/…E.G/.From
ﬁniteness of EndGwe get an idempotent powerf
i
off,i.e..f
i
/
2
Df
i
, and thus
f
i
2HEndG; see Remark 1.5.9. In particular, since.f
i
.x/; f
i
.x
0
//2E.G/,we
have thatf
i
.x/andf
i
.x
0
/are ﬁxed underf
i
, and thus they are adjacent preimages.
Moreover,f
i
…SEndGsince not all preimages are adjacent, in particular.x; x
0
/…
E.G/.
Before analyzing the endotypes of graphs in more detail, we consider all endotypes
with regard to whether or not AutGD1.
Proposition 1.7.3.jAutGjD1impliesjSEndGjD1.
Proof.Takef2SEndGnAutG. Then there existx;x
0
2V.G/,x¤x
0
, with
f.x/Df.x
0
/andN.x/DN.x
0
/by Proposition 1.5.5. Then the mapping which
permutes exactlyxandx
0
is a non-trivial automorphism ofG.
The preceding result shows that for endotypes 16 up to 31 we always have
AutG¤1, since SEndG¤AutGin these cases. So we add for endotypes 0 to
15 an additionaladenoting asymmetry, if AutGD1.
We can say that endotype 0 describes unretractive graphs and endotype0adescribes
rigid graphs. Endotypes 0 up to 15 describe S-A unretractive graphs, and endotypes
0a;2a;:::;15adescribe asymmetric graphs. Endotype 16 describes E-S unretractive
graphs which are not unretractive. Endotype 31 describes graphs for which all six sets
are different.

20 Chapter 1 Directed and undirected graphs
Theorem 1.7.4.There exist simple graphs without loops of endotype0;0a;2;2a;3;
3a;:::;15;15a;16;18;19;:::;31.
Proof.See M. Böttcher and U. Knauer,Endomorphism spectra of graphs, Discrete
Math. 109 (1992) 45–57, andPostscript “Endomorphism spectra of graphs”, Discrete
Math. 270 (2003) 329–331.
The following result is an approach to the question of to what extent trees are de-
termined by their endospectrum. It also shows that the endospectrum in general does
not determine graphs up to isomorphism.
Theorem 1.7.5.LetGbe a tree, withG¤K
2. The following table characterizesG
with respect to endotypes, which are given by their decadic coding in the ﬁrst column
and explicitly in the second column. Classes of endomorphisms are abbreviated by
their ﬁrst letters, and
G¤indicates the existence of two different vertices in
Gwhich have exactly the same neighbors; cf. Deﬁnitions9:5:1and10:2:2.Forthe
notation in the last column, see the generalized lexicographic product in Section4:4.
Examples or
N
0
Endotype G diamcomplete descriptions
6EDH¤L¤QDSDAD4P4is the smallest
10EDH¤LDQ¤SDADD3P3is the only one
16EDHDLDQDS¤A¤D2Exactly the stars, i.e.K 1;nfor
n2
22EDH¤L¤QDS¤A¤4P4with one end-vertex
doubled,
i.e.P
4ŒK2;K1;K1;K1;K1,
is the smallest
26EDH¤LDQ¤S¤A¤D3Exactly the “double stars”,
namelyP
3with at least one
end-vertex at least doubled,
i.e.P
3Œ
Kn;K1;K1;Kmwith
n2orm2
Asymmetric treesG,i.e.Gsuch thatjAutGjD1, are possible only with endotype6;
in other words, they have endotype6a. The smallest is the path of length5, with one
pending vertex at the third vertex, i.e. a vertex of degree1.
A proof follows after Proposition 1.7.15.

Section 1.7 The endomorphism type of a graph 21
Lemma 1.7.6.AtreeGwithdiam.G/D3is a double star.
Proof.Let¹x
0
0
;x0;x1;x
0
1
ºbe a longest simple path inG. The only possibility for
adding edges inGwithout changing the diameter or destroying the tree property is
thatx
0orx1have additional neighbors of degree 1.
Lemma 1.7.7.LetGbe a graph such thatN.x/¤N.x
0
/for somex;x
0
2Gwith
.x; x
0
/…E.G/.ThenHEndG¤LEndG.
Proof.Deﬁnef.x/Df.x
0
/Dx
0
andf.y/Dyfor ally¤x2G.Then
obviouslyf2HEndG.Butf…LEndG, because forx
00
2N.x
0
/nN.x/one
has.f .x
00
/; f .x//D.x
00
;x
0
/2E.G/,f
1
.x
00
/D¹x
00
º,f
1
.x
0
/D¹x;x
0
ºbut
.x; x
00
/…E.G/, i.e. not every preimage ofx
0
is adjacent to some preimage ofx
00
.
The following two lemmas are clear.
Lemma 1.7.8.SupposeGis a tree withx;x
0
2Gsuch thatN.x/¤N.x
0
/.Then
diam.G/3.
Lemma 1.7.9.LetGbe a tree withdiam.G/3.Takex;x
0
;x
00
2Gwith¹x
0
ºD
N.x/¤N.x
0
/?x;x
00
º. Then, by deﬁningf.x/Dx
00
andf.y/Dyfory¤x,
we getf2HEndGnLEndG.
Lemma 1.7.10.LetGbe a double star as in Lemma1:7:6.ThenQEndG¤SEndG.
Proof.Take¹x
0
0
;x0;x1;x
0
1
ºfrom Lemma 1.7.6, a longest simple path inG.Deﬁne
f.N.x
0//D¹x 1ºandf.N.x 1//D¹x 0º.Thenf2QEndG, sincex 12f
1
.x1/is
adjacent to every vertex inN.x
1/Df
1
.x0/andx 02f
1
.x0/is adjacent to every
vertex inN.x
0/Df
1
.x1/.Butf…SEndGas.x
0
0
;x
0
1
/…E.G/.
Proposition 1.7.11.LetGbe a tree withdiam.G/4.ThenQEndGDSEndG.
Proof.Takef2QEndG. Then there exists.x; x
0
/2E.G/such that.f .x/; f .x
0
//2
E.G/, and we may assume thatxandx
0
are central with respect to.f .x/; f .x
0
//.
ThenUWDf
1
.f .x//N.x
0
/andU
0
WDf
1
.f .x
0
//N.x/. As diam.G/
4, there existsy2N.U
0
/such that.y;
x
0
/2E.G/for somex
0
2U
0
.Then
.f .y/; f .x
0
//D.f .y/; f .x
0
//2E.G/, and sincef2QEndGwe get thaty,
say, is adjacent to all vertices inU
0
, and hence tox
0
in particular. But thenjU
0
jD1,
because otherwise there would be a cycle¹y;x
0
;x;
x
0
;y/inG, which is impossible
sinceGis a tree. Moreover, every vertex inUhas degree 1 with the common neighbor
x
0
. Together with Proposition 1.5.5, this implies thatf2SEndG.Proposition 1.7.12.IfGis a tree withdiam.G/4,thenLEndG¤QEndG.

22 Chapter 1 Directed and undirected graphs
Proof.As diam.G/4, the tree containsP 4D¹x 0;x1;x2;x3;x4º.DeﬁnefW
G!Gas follows: all vertices with even distance fromx
2are mapped ontox 2; all
other vertices are mapped ontox
1.
Thenf2LEndG, since every preimage ofx
2is adjacent to some preimage of
x
1and vice versa. Butf…QEndGbecause no vertex exists in the preimage ofx 1
which is adjacent tox 0and tox 4,asGhas no cycles.
Lemma 1.7.13.For starsGDK 1;none hasEndGDSEndG.
Proof.We may assume thatn>1.Ifjf.G/j>2for an endomorphismf, the central
vertex of the star is ﬁxed and thereforefis strong. Ifjf.G/jD2,i.e.f.G/DK
2,
thenfis also strong.
Proposition 1.7.14.LetG¤K 2be a tree withdiam.G/3.ThenLEndGD
QEndG.
Proof.IfG¤K
2is a tree with diam.G/3,thenGis a star or a double star.
In the ﬁrst case, the statement is contained in Lemma 1.7.13. So letGbe a double
star, i.e. suppose that there existx
0;x12GwithV.G/DN.x 0/
S
N.x 1/and
.x
0;x1/2E.G/.Takef2LEndG. Then it is impossible to havef.y/Dx 1and
f.y
0
/¤x 1fory;y
0
2N.x0/n¹x1º.Sofidentiﬁes only vertices insideN.x 0/n¹x1º
or insideN.x
1/n¹x 0º, possibly followed by an automorphism of the resulting graph,
and we havef2SEndG.
Proposition 1.7.15.For any graphGone hasSEndGDAutGif and only ifR GD
,i.e.N.x/¤N.x
0
/for allx¤x
0
2G.
Proof.If the verticesx¤x
0
have the same neighbors, thenf.x/Dx
0
is a non-
bijective strong endomorphism, provided all other vertices are ﬁxed.
Proof of Theorem1:7:5.It is clear that the third column of the table covers all possible
trees.
The ﬁrst column of equalitiesEDHis obvious for all trees.
In the second column, the inequalitiesH¤Lare furnished by Lemmas 1.7.9 and
1.7.7. The equalityHDLfor type 16 is taken care of by Lemma 1.7.13.
The inequalitiesL¤Qare provided by Proposition 1.7.12, and the equalities
LDQare given by Proposition 1.7.14.
The equalitiesQDSare taken care of by Proposition 1.7.11 and for type 16 again
by Lemma 1.7.13. The inequalities are given by Lemma 1.7.10, noting thatP
3is also
a double star.
The relations betweenSandAcome from Proposition 1.7.15.
Now consider the “examples” and “complete descriptions” in the last column of
Theorem 1.7.5. The statements about endotypes 6, 10 and 22 follow, by inspection,

Section 1.7 The endomorphism type of a graph 23
from what was said about Gand diam. The statement about endotype 16 follows
from Lemma 1.7.13 together with the fact that
G¤and diam.G/D2.The
statement about endotype 26 is Lemma 1.7.6.
The last assertion about asymmetric trees is also implied by 4.13 in R. Novakovski
and I. Rival,Retract rigid Cartesian products of graphs, Discrete Math. 70 (1988)
169–184. Indeed,jAutGjD1is possible only if SEndGDAutG(see Proposi-
tion 1.7.3), i.e. only for endotypes smaller than 16; so in our situation only endotype
6 remains.
The statement concerning the smallest examples follows by inspection.
In the following table we use the union and the multiple union of graphs in a naive
way. A formal deﬁnition (as coproduct) will follow in Chapter 3.
Theorem 1.7.16.Bipartite graphs are exactly of the following endotypes, where the
graphs or their common structures are given where possible.
EndotypeGraph EndotypeGraph
0 K2 16 Kn;K1;n,n2
2 K1
S
K
2
18 Kn
S
K
2,n2
4
S
n2
K219 Kn
S
.
S
n2
Kn/,Km
S
K
1;n,n2,m1
6 22
7 23
10 P3 26 “double stars”
11 27
15 31
Proof.See U. Knauer,Endomorphism types of bipartite graphs,inM.Ito,H.Jür-
gensen (eds.), Words, Languages and Combinatorics II, pp. 234–251, World Scien-
tiﬁc, Singapore 1994.
Note that adding an isolated vertex to a connected graph which is not of endotype 0
or 16 adds 1 to the value of the endotype. This gives examples of graphs of endotypes
7, 11, 23 and 27 when starting with suitable trees from Theorem 1.7.5. The procedure
yields graphs with endotype 2 or 18 when starting with graphs of endotype 0 or 16.
Question.For which of the trees in Theorem 1.7.5 do the sets which are not monoids
in general form monoids? The question makes sense for LEnd and endotypes 6,10,22
and 26.
It seems possible that trees are determined by their endomorphism spectrum up
to isomorphism. Obviously this is not the case for the endotype. Would this be a

24 Chapter 1 Directed and undirected graphs
worthwhile question to investigate? Some more information about this can be found
in U. Knauer,Endomorphism types of trees, in M. Ito (ed.), Words, Languages and
Combinatorics, pp. 273–287, World Scientiﬁc, Singapore 1992.
1.8 Comments
Ordinary homomorphisms are widely used. Half-strong homomorphisms were called
“full” in P. Hell,Subdirect products of bipartite graphs(Coll. Math. Janos Bolyai 10,
Inﬁnite and ﬁnite sets, 1973, Vol II), pp. 875–866, North Holland, Amsterdam 1975,
and in G. Sabidussi,Subdirect representations of graphs(Coll. Math. Janos Bolyai
10, Inﬁnite and ﬁnite sets, 1973, Vol III), pp. 1199–1226, North-Holland, Amsterdam
1975; and they were called “partially adjacent” by S. Antohe and E. Olaru inOn
homomorphisms and congruences of graphs, Bull. Univ. Galat 11 (1978) 15–23 (in
German).
Surjective locally strong homomorphisms appeared in the book by A. Pultr and
V. Trnkova,Combinatorial, Algebraic and Topological Representations of Groups,
Semigroups and Categories, North-Holland, Amsterdam 1980. As far as I know, the
term “quasi-strong” has not been used yet. Strong homomorphisms were ﬁrst intro-
duced by K. Culik inOn the theory of graphs, Casopis Pest. Mat. 83 (1958) (in
German), under the name homomorphism. Metric homomorphisms can be found in
the aforementioned paper by P. Hell. Egamorphisms are also called weak homomor-
phisms, for example in [Imrich/Klavzar 2000].
I would like to point out a more general phenomenon. Homomorphisms generate
an image of a given object. This is the basis of the main principle of model building:
we can view homomorphisms as the modeling tool and the homomorphic image as
the model. When we use isomorphisms, all the information is retained. Since a model
is usually thought of as a simpliﬁcation, an isomorphic image is not really the kind of
model one usually needs. So, in modeling, we want to suppress certain information
about the original object, because in order to analyze the system it is helpful to ﬁrst
simplify the structure. To investigate different questions we may wish to suppress dif-
ferent parts of the structure. Specializing this idea to graphs, strong homomorphisms
reduce the number of points but maintain the structure in the sense that they reﬂect
edges. Quasi-strong, locally strong and half-strong homomorphisms reﬂect edges to a
lesser and lesser extent in each step down to ordinary homomorphisms, which do not
reﬂect edges at all.
Now let us also look back on the Homomorphism Theorem. One important aspect
is that it produces an epi-mono factorization for every homomorphism. This is ex-
ploited in the following way. We start with one endomorphismfofG, which by the
induced congruence%
fdeﬁnes the epi- part of the epi-mono factorization, the natural
surjectionG!G=%
f. If we now consider all possible embeddings of this factor
graph intoG, we obtain all possible endomorphisms with the induced congruence%
f.

Section 1.8 Comments 25
This principle can be used to ﬁnd all endomorphisms of an objectG. This is done,
for example, when we prove that the set LEndP
nfor a path of lengthnis a monoid if
and only ifnD3ornC1is prime; see Section 9.3.
Recall that the Homomorphism Theorem gives especially nice approaches to group
and ring homomorphisms. In these two cases (categories), induced congruences are
uniquely described by subobjects, namely normal subgroups in groups, also called
normal divisors, and ideals in rings. These objects are much easier to handle than
congruence relations; thus the investigation of homomorphisms in these categories
is – to some extent – easier. For example, every endomorphism of a groupAis
determined by the factor groupA=N,whereNis a normal subgroup ofA, and all
possible embeddings ofA=NintoA. See also Project 9.1.8. Nothing similar can be
done for semigroups or in any of the graph categories (which will be introduced later).

Chapter 2
Graphs and matrices
Matrices are very useful for describing and analyzing graphs. In this chapter we
shall present most of the common matrices for graphs and apply them to investigate
various aspects of graph structures, such as isomorphic graphs, number of paths or
connectedness, and even endomorphisms and eigenvalues. All of this analysis is based
on the so-called adjacency matrix.
We also deﬁne another important matrix, the so-called incidence matrix, which we
will use later when discussing cycle and cocycle spaces.
2.1 Adjacency matrix
The deﬁnition of the adjacency matrix is the same for directed and undirected graphs,
which may have loops and multiple edges.
Deﬁnition 2.1.1.LetGD.V;E;p/whereVD¹x
1;:::;xnºis a graph. Thenn
matrixA.G/D.a
ij/i;jD1;:::;ndeﬁned by
a
ijWD
ˇ
ˇ
¹e2Ejp.e/D.x i;xj/º
ˇ
ˇ
is called theadjacency matrixofG.
Example 2.1.2(Adjacency matrices). We show the “divisor graph” of 6 and a multi-
ple graph, along with their adjacency matrices.
3
A.G/D
0
B
B
@
0111
0001
0001
0000
1
C
C
A
1
2
3
6
1
6
2

3
A.G/D
0
@
020
100
011
1
A
2
1

Remark 2.1.3.There exists a bijective correspondence between the set of all graphs
with ﬁnitely many edges andnvertices and the set of allnnmatrices overN
0.

Section 2.1 Adjacency matrix 27
It is clear that if the matrixA.G/is symmetric, then the graphGis symmetric (i.e.
undirected) and vice versa.
IfGis simple, i.e. if it does not have multiple edges, then we can deﬁneA.G/by
a
ijWD
²
1if.x
i;xj/2E;
0otherwise.
Proposition 2.1.4.For allx
i2VwithA.G/D.a ij/
i;j2jVjDn we have
indeg.x
i/D
n
X
jD1
aji;column sum of columni;
outdeg.x
i/D
n
X
jD1
aij;row sum of rowi.
In the symmetric case one has
deg.x
i/D
n
X
jD1
aijD
n
X
jD1
aji:
Example 2.1.5(Adjacency matrix and vertex degrees). This example shows that the
row sums ofA.G/are the outdegrees of the vertices and the column sums are the
indegrees.

v3 v4
v2 v1
v5
x1x2x3x4x5 row sum
v
1 00000 0
v
2 10110 3
v
3 10000 1
v
4 00100 1
v
5 00000 0
column sum 2 0 2 1 0

28 Chapter 2 Graphs and matrices
Isomorphic graphs and the adjacency matrix
The next theorem gives a simple formal description of isomorphic graphs. It does
not contribute in an essential way to a solution of the so-calledisomorphism problem,
which describes the problem of testing two graphs for being isomorphic. This turns
out to be a real problem if one wants to construct, for example, all (non-isomorphic)
graphs of a given order.
Theorem 2.1.6.LetGD.V; E/andG
0
D.V
0
;E
0
/be two simple graphs with
nDjVj. The homomorphism
fWGD.V; E/!G
0
is an isomorphism if and only if there exists a matrixPsuch that
A.G
0
/DPA.G/P
1
;
wherePis annnrow permutation matrix which comes from the identity matrixI
n
upon performing row permutations corresponding tof.
Proof.For “)”, supposeGŠG
0
,i.e.thatG
0
comes fromGby permutation of
the vertices. Then, inA.G/, rows and columns are permuted correspondingly. Thus
A.G
0
/DPA.G/P
1
,wherePis the corresponding row permutation matrix. Left
multiplication byPthen permutes the rows and right multiplication byP
1
permutes
the columns.
For “(”, supposeA.G
0
/DPA.G/P
1
wherePis a permutation matrix. Then
there exists a mappingfWV!V
0
with
.x
i;xj/2E;i.e.a ijD1,a
f .i /;f .j /D1;i.e..x
f.i/;x
f.j//2E
0
:
Example 2.1.7(Isomorphisms and adjacency matrices). It is apparent that the graphs
GandG
0
are isomorphic. The matrixPdescribes the permutation of vertex numbers
which leads fromA.G/toA.G
0
/,i.e.A.G
0
/DPA.G/P
1
.
G G
0
13
2
13
2
f

Section 2.1 Adjacency matrix 29
PD
0
@
010
001
100
1
A;P
1
D
t
P;
A.G/D
0
@
010
001
110
1
A;A.G
0
/D
0
@
010
101
100
1
A:
Components and the adjacency matrix
Simple matrix techniques enable restructuring of the adjacency matrix of a graph
according to its geometric structure.
Theorem 2.1.8.The graphGhass(weak) componentsG
1;:::;Gsif and only if
there exists a permutation matrixPwith
PA.G/P
1
D
0
B
B
B
@
A.G
1/0
A.G
2/
:
:
:
0A.G
s/
1
C
C
C
A
(block diagonal form).
Proof.Weak connectedness deﬁnes an equivalence relation onV,sowegetade-
composition ofVintoV
1;:::;Vs. These vertex sets induce subgraphsG 1;:::;Gs.
RenumberGso that we ﬁrst get all vertices inG
1, then all vertices inG 2, and so on.
Note that there are no edges between different components.
Theorem 2.1.9.The directed graphGhas the strong componentsG 1;:::;Gsif and
only if there exists a permutation matrixPwith
PA.G/P
1
D
0
B
B
B
@
A.G
i1
/
A.G
i2
/
:
:
:
0A.G
is
/
1
C
C
C
A
(Frobenius form, block triangular form).
Proof.If we have the strong components, selectG
i1
so that no arrows end inG i1
.
Then selectG
i2
so that except for arrows starting fromG i1
,noarrowsendinG i2
.
Note that there may be no arrows ending inG
i2
. Next, selectG i3
so that except for
arrows starting fromG
i1
or fromG i2
,noarrowsendinG i3
. Continue in this fashion.
Observe that the numbering inside the diagonal blocks is arbitrary. The vertices ofG
have to be renumbered correspondingly.

30 Chapter 2 Graphs and matrices
Example 2.1.10(Frobenius form).
3 2
1

5
4

Gi1
Gi2
0
B
B
B
B
@
01010
00100
10000
00001
00010
1
C
C
C
C
A
Adjacency list
The adjacency list is a tool that is often used when graphs have to be represented in a
computer, especially if the adjacency matrix has many zeros.
Deﬁnition 2.1.11.Theadjacency listA.x/of the vertexx2Gin the directed case
consists of all successors ofx, i.e. the elements of out.x/in arbitrary order. In the
undirected case it consists of all neighbors ofxin arbitrary order.
Theadjacency listof the graphGisA.x
1/IA.x2/I:::forx i2G.
Example 2.1.12.The adjacency list of the graph from Example 2.1.10 is
A.1/D2;4IA.2/D3IA.3/D1IA.4/D5IA.5/D4:
If the graphGhas multiple edges, then the outsets in its adjacency list may contain
certain elements several times; in this case we get so-called multisets.
2.2 Incidence matrix
The incidence matrix relates vertices with edges, so multiple edges are possible but
loops have to be excluded completely. It will turn out to be useful later when we
consider cycle and cocycle spaces. Its close relation to linear algebra becomes clear
in Theorem 2.2.3. We give its deﬁnition now, although most of this section relates to
the adjacency matrix.

Section 2.3 Distances in graphs 31
Deﬁnition 2.2.1.TakeGD.V;E;p/, withVD¹x 1;:::;xnºandED¹e 1;:::;emº.
ThenmmatrixB.G/over?1; 0; 1ºwhere
b
ijWD
8
<
:
1ifx
iDo.ej/
1ifx
iDt.ej/
0otherwise
or, in the undirected case,
b
ijWD
²
1ifx
i2ej
0otherwise
is called the(vertex–edge) incidence matrixofG.
Example 2.2.2(Incidence matrix). Here we present the incidence matrix of the divi-
sor graph of 6; see Example 2.1.2. The matrix is the inner part of the table.
2
6
13

a
b
d e
c
abcde
101011
2100 10
30010 1
611100
Theorem 2.2.3.LetGbe a graph withnvertices ands(weak) components, and
without loops. ThenB.G/has rankns(overZ
2in the undirected case), and when
sD1anyn1rows ofB.G/are linearly independent.
Proof.We number the vertices according to Theorem 2.1.8 (block diagonal form),
and getB.G/also in block diagonal form. Its rank is the sum of the ranks of the
blocks. So we considersD1. Addition of the row vectors gives the zero vector;
therefore the rows are linearly dependent, i.e. we have rank.B.G//n1.Ifwe
delete one row, i.e. one vertex, then the sum of the remaining row vectors is obviously
not zero.2.3 Distances in graphs
We now consider reachability and distances in graphs. For each graph, these can again be represented by matrices.

32 Chapter 2 Graphs and matrices
Deﬁnition 2.3.1.TakeGD.V; E/withVD¹x 1;:::;xnº.ThennmatrixR.G/
with
r
ijWD
²
1if there exists a non-trivialx
i;xjpath
0otherwise
is called thereachability matrixofG.
The reachability matrix also shows the strong components of a graph.
Note that there may be a problem with the diagonal. In the deﬁnition we have
r
iiD1if and only ifx ilies on a cycle. It is also possible to set all diagonal elements
to0or1. This choice can be made when the graph models a problem that allows us
to decide whether a vertex can be reached from itself if it lies on a cycle.
Deﬁnition 2.3.2.TakeGD.V; E/and use the notation from Deﬁnition 1.1.5. The
matrixD.G/with
d
ijWD
8
<
:
1 ifF.x
i;xj/D;andi¤j
0 ifiDj
d.x
i;xj/otherwise
is called thedistance matrixofG.The.i; j /th element of the distance matrix is the
distance from vertexx
ito vertexx j, and is inﬁnity if no path exists.
The adjacency matrix and paths
A simple but surprising observation is that the powers of the adjacency matrix count
the number of paths from one vertex to another. We start with an example.
Example 2.3.3(Powers of the adjacency matrix).
3
1
4
2

GW
0
B
B
@
0101
1001
1000
1000
1
C
C
A
2
D
0
B
B
@
2001
1101
0101
0101
1
C
C
A
DA.G/
2
HwithA.H/D.A.G//
2
:
3
1
4
2

Section 2.3 Distances in graphs 33
Theorem 2.3.4.TakeGD.V;E;p/and leta
.r/
ij
be an entry of.A.G//
r
.Thena
.r/
ij
is the number ofx i;xjpaths of lengthrinG.
Proof.The result follows from the formula for the second power,
a
.2/
ij
D
n
X
kD1
a
ika
kj;
together with induction. This is the formula for the entries in the product of matrices.
Remark 2.3.5.Note that forming the second power of an adjacency matrix can be
generalized to taking the product of two adjacency matrices of the same size. The
result can be interpreted as a graph containing as its edges the corresponding paths of
length two. A similar method works for products of more than two matrices. In all
cases, the resulting graph depends on the numbering.
If, conversely, we start from a given graphGand construct the graphG
2
of paths of
length two, and then perform the corresponding steps withA.G/, we automatically get
the matrix productA.G/
2
without having to know its deﬁnition from linear algebra.
The adjacency matrix, the distance matrix and circuits
The following remark and two theorems are obvious.
Remark 2.3.6.IfjVjDn, then the length of a simple path inGis at mostn.Ifthe
length equalsn, then the path is a circuit.
Theorem 2.3.7.LetGbe a graph withnvertices. The elements of the distance matrix
D.G/can be obtained from the powers ofA.G/as follows:
(a)d
iiD0for alli;
(b)d
ijis the smallestr2Nwitha
.r/
ij
>0andr<n,ifsuchanrexists;
(c)d
ijD1otherwise.
For the elements of the reachability matrixR.G/we have:
(a)r
iiD0for alli;
(b)r
ijD1if and only if there existsr<nwitha
.r/
ij
>0;
(c)r
ijD0otherwise.
Theorem 2.3.8.The graphGcontains no circuits if and only ifa
.r/
ii
D0in.A.G//
r
forrnand for alli.

34 Chapter 2 Graphs and matrices
2.4 Endomorphisms and commuting graphs
We brieﬂy discuss two aspects of the adjacency matrix which have not gained much
attention so far.
Deﬁnition 2.4.1.Letfbe a transformation of the ﬁnite set¹1;:::;nº, i.e. a mapping
of the set into itself. Deﬁne thetransformation matrixT.f/D.t
ij/
i;j2¹1;:::;nº off
by setting itsith rowt
ito be
0C
P
f.j/Di
ej,wheree jis thejth row of the identity
matrixI
nand
0is the row of zeros withnelements.
This means that theith row ofTconsists of the sum of rowse
jsuch thatjis
mapped ontoibyf.
For the following, start by verifying some small examples.
Exerceorem 2.4.2.
(1) The transformationfis an endomorphism of the graphGwith vertex set
¹x
1;:::;xnºand adjacency matrixA.G/if and only if the.i; j /th entry of
T.f/A.G/
t
T.f/being non-zero implies that the.i; j /th entry ofA.G/is non-
zero.
(2) The transformationfis an endomorphism of the graphGwith vertex set
¹x
1;:::;xnºand incidence matrixB.G/if and only if thejth column of
T.f/B.G/having non-zero entries implies that there exists a column ofB.G/
which has the same non-zero entries in the same places.
Deﬁnition 2.4.3.We say thatGandH(with the same number of vertices) arecom-
muting graphsif there exist labelings of the graphs such that their adjacency matrices
commute, i.e.A.G/A.H/DA.H/A.G/.
Theorem 2.4.4.The graphGcommutes withK
nif and only ifGis a regular graph;
it commutes withK
n;nifGis a regular subgraph ofK n;n.
Proof.See A. Heinze,Construction of commuting graphs, in: K. Denecke and
H.-J. Vogel (eds.), General Algebra and Discrete Mathematics: Proceedings of the
Conference on General Algebra and Discrete Mathematics in Potsdam 1998. Shaker
Verlag, 1999, pp. 113–120. In addition, there we have a construction of new commut-
ing graphs starting with two pairs of commuting graphs.
Question.Can you ﬁnd a counterexample for the open “only if” part of the theorem?
Construct some positive examples and some negative ones.

Random documents with unrelated
content Scribd suggests to you:

kenties tapahtui siitä syystä, että Mihiei Mihieitsh syödessään otti
toisenkin ryypyn viinaa. Korttia jaettaessa hän sanoi jo edeltäpäin
tietävänsä, että kaikki ässät ja valtit joutuvat Onufrij'ille, hänellä kun
on sellaiset näpistelijän kädet, jotka aina ovat valmiit sekoittamaan
väärin ja anastamaan parhaat kortit. Mutta tehtyään hänen kanssaan
korttilietteen, Mihiei Mihieitsh muuttui kokonaan ja alkoi häntä
kehua.
— No tietysti sinä olet, sano mitä tahansa, koko hylky mieheksesi,
— puheli hän hänelle: mutta minä pidän sinusta, jumal'avita, pidän
kun pidänkin; sentähden, ensinnäkin, että minulla on sellainen
luonto, ja toiseksi, jos asiaa tarkemmin harkitsee, niin on niitä
suurempiakin heittiöitä kuin sinä, täytyypä vielä sanoa, että sinä
sentään olet laadussasi koko mukiinmenevä mies.
— Siinä oli perää siinä puheessa, minkä nyt arvoisilta huuliltanne
kuulin, Mihiei Mihieitsh, — vastasi Onufrij Ilitsh, joka tunsi kuin
nousevansa noista sanoista: — ihan perujen perää oli siinä;
tietenkin, vaan vainoamista…
— Ja'a kortit, ja'a kortit, — keskeytti hänet Mihiei Mihieitsh: —
ettäkö vainoamista? mitä vainoamista? Kiitä Jumalaasi, ett'et istu
tällä hetkellä Pugatshovin [Kuuluisa kasakkapäällikkö,
kapinanjohtaja, joka m.m. esiintyy henkilönä Pushkinin "Kapteenin
tyttäressä." Suoment. muist.] tornissa, kahleisiin kytkettynä… Ja'a
kortit.
Ja Onufrij Ilitsh alkoi jakaa, vilkuttaen silmiään ja kastaen kiireesti
oikean käden sormea pitkän, kapean kielensä päähän.
Mutta Stepan Petrovitsh yhä kulki edes takaisin, ja Boris Andrejitsh
pysytteli Veeran läheisyydessä. Heidän keskustelunsa oli katkonaista

(Veera kävi ehtimiseen ulkona) ja niin vähäpätöistä, että olisi vaikea
ruveta sitä kuvaamaan. Boris Andrejitsh kysyi häneltä, ketä
naapureita heillä on, matkustaako hän usein pois kotoaan,
rakastaako hän taloutta. Kysymykseen, mitä hän lukee, hän vastasi:
"lukisin, mutt'ei ole aikaa!" Ja kun keskustelun kestäessä poika tuli
ilmoittamaan, että hevoset olivat valjaissa, oli hänestä ikävä lähteä,
ikävä heretä katselemasta noita hyviä silmiä, tuota kirkasta hymyilyä.
Jospa Stepan Petrovitshin mieleen olisi juolahtanut pyytää heitä
jäämään, olisi hän varmasti suostunut. Mutta Stepan Petrovitsh ei
pyytänyt, ei siksi, ett'ei hän olisi iloinnut uudesta vieraastaan, vaan
siksi, että hänellä oli sellainen tapa: joka tahtoi yöpyä, hän sai
kursailematta tilata itselleen vuoteen. Niin tekivät Mihiei Mihieitsh ja
Onufrij Ilitsh, jopa asettuivat makaamaan samaan huoneeseen ja
pakisivat kauan yli puolenyön; heidän äänensä kuuluivat kumeina
seinän läpi; enemmän puhui Onufrij Ilitsh, tai ehkä oikeammin kertoi
jotakin, vakuutteli jotakin, mutta hänen toverinsa vaan äännähti
puheen väliin, milloin epäilevästi, milloin rohkaisevasti "hm!"
Seuraavana aamuna he läksivät ajamaan Mihiei Mihieitshin kylään, ja
sieltä kaupunkiin, sinnekin yhdessä.
Paluumatkallaan Pietari Vasiljitsh ja Boris Andrejitsh kauan istuivat
ääneti. Pietari Vasiljitsh nukahti aisakellon yksitoikkoiseen
nalkutukseen ja reen tasaiseen, tuudittavaan kulkuun.
— Pietari Vasiljitsh! — sanoi Boris Andrejitsh vihdoin.
Mitä? — kysyi Pietari Vasiljitsh kuin unesta.
— Miksi ette kysele minulta mitään?
— Mitä tässä nyt olisi kysellä?

— Samaa kuin aina ennenkin — näillä matkoillamme?
— Veerotshkastako nyt?
— Niin!
— Siinä nyt oli! Pitäisikö minun kysyä, kun tiedän, että hän ei teille
kelpaa.
— Turhaan te sellaista luulette. Hän miellyttää minua paljon
enemmän, kuin kaikki teidän Emerentsianne ja Sofia Kirillovnanne.
— Mitä te nyt?
— Sen sanon teille.
— Pyydän, olkaahan nyt! — onhan hän aivan yksinkertainen
neitonen. Hyvä emäntä hän kyllä saattaa olla, — se on selvä; mutta
tarvitsetteko te sellaista?
— No, miksen? Ehkäpä minä etsinkin juuri sellaista.
— Mutta, Boris Andrejitsh, malttakaa! eihän hän puhu
ranskaakaan?
Pietari Vasiljitsh vaikeni.
— Minä en odottanut teiltä sellaista… teiltä, sanon minä…
varmaankin te laskette leikkiä.
— En ensinkään.
— Jumala teidät sitten yksin tuntenee! Minä olen aina pitänyt
häntä vaan meikäläiselle miehelle sopivana. Mutta muuten, hän on

neitonen, joka pystyy mihin tahansa.
Ja Pietari Vasiljitsh korjasi lakkiansa, painoi päänsä tyynyyn ja
nukahti. Boris Andrejitshin ajatukset vaan yhä asustivat Veerotshkan
luona. Hänen edessään väikkyi hänen hymyilynsä ja silmiensä iloinen
lempeys. Yö oli kirkas ja kylmä, lumi välkkyi kuin timanttinen
hohtovaippa; taivaalla olivat tähdet syttyneet tuikkimaan, pakkanen
paukkui ja kitisi jalasten alla; puiden oksissa kimalteli jäinen kuura.
Sellaisina hetkinä mielikuvitus nousee siivilleen. Vjasovnin sai kokea
sen. Mitä kaikkea hän lieneekään mietiskellyt. Reki viimein pysähtyi
portaiden eteen. Mutta Veerotshkan kuva ei häipynyt vielä silloinkaan
hänen mielestään, vaan salaa seurasi häntä unen helmoihin.
Pietari Vasiljitsh, kuten sanottu, oli ihmeissään siitä vaikutuksesta,
jonka Veerotshka oli Boris Andrejitshiin tehnyt, mutta hän ihmetteli
vielä enemmän, kun Boris Andrejitsh parin päivän kuluttua ilmestyi
hänen luoksensa kertoen välttämättä haluavansa lähteä Barsukoviin,
ja lupasi lähteä yksin, ell'ei Pietari Vasiljitsh tulisi mukaan. Pietari
Vasiljitsh tietysti oli iloinen ja valmis tulemaan, ja niin ystävykset
taaskin lähtivät ja viipyivät perillä kokonaisen päivän. Kuten ensi
kerralla, oli nytkin Barsukovin luona muutamia vieraita joita Veera
kestitsi kahvilla ja kahvin jälkeen hillolla; mutta Vjasovnin puheli
hänen kanssaan enemmän kuin edellisellä kerralla, ja nimenomaan
juuri hänelle. Hän kertoi hänelle entisyydestään, Pietarista,
matkoistaan, — sanalla sanoen kaikesta, mikä hänen mieleensä
juolahti. Hän kuunteli häntä rauhallisesti ja tarkkaavasti milloin
hymyillen katsellen häntä, mutta hetkeksikään unohtamatta
emännäntoimia, heti hän nousi, kun huomasi vieraiden jotain
tarvitsevan, ja läksi itse asiaa toimittamaan. Hänen poistuessaan
Vjasovnin yhä pysyi liikkumatta paikallaan, ja palattuaan Veera istui
käsitöineen hänen vierelleen jatkaakseen keskustelua. Stepan

Petrovitsh, joka kulki huoneessa edestakaisin, seisahtui toisinaan
heidän eteensä, kuunteli Vjasovnin puheita ja sanoi: "brau, brau!" —
ja niin aika kului. Tällä kertaa Vjasovnin ja Pietari Vasiljitsh jäivät
yöksi ja lähtivät paluumatkalle vasta seuraavan päivän illalla…
Hyvästellessään Vjasovnin puristi Veerotshkan kättä. Veerotshka
punastui. Ei kukaan mies ennen sitä päivää ollut puristanut hänen
kättänsä, mutta hän ajatteli, että niin mahtaa Pietarissa olla tapana.
Molemmat ystävät alkoivat usein käydä Stepan Petrovitshin luona,
erittäinkin Boris Andrejitsh tunsi jo olevansa siellä melkein kuin
kotonaan. Hän tunsi alituista vetovoimaa sinne. Muutaman kerran
hän kävi siellä yksinkin. Veerotshka alkoi miellyttää häntä yhä
enemmän; heidän välilleen syntyi ystävyys. Pietari Vasiljitsh ei enää
puhunut hänelle Veerasta niinkuin ennen… Mutta eräänä aamuna
kun Pietari Vasiljitsh oli katsellut häntä jonkun aikaa äänettömänä,
sanoi hän:
— Boris Andrejitsh!
— Mitä? — vastasi Boris Andrejitsh ja punastui hieman itsekään
tietämättä miksi.
— Mitäkö minä aioin teille sanoa, Boris Andrejitsh… Te katsotte…
sitä… mutta ei ole hyvä, ja, esimerkiksi, jotain…
— Mitä te oikeastaan tarkoitatte, vastasi Boris Andrejitsh: — en
ymmärrä teitä.
— Niin, tarkoitin Veerotshkaa…
— Veerotshkaako?
Ja Boris Andrejitsh punastui vielä enemmän.

— Niin. Suokaa anteeksi, jos olen suora; mutta katson
velvollisuudekseni ystäväni…
— Mistä te olette tuollaisia keksineet Pietari Vasiljitsh? — keskeytti
hänet Boris Andrejitsh. — Veerotshka — on nainen, hieno ja ankara
itseään kohtaan, ja meidän välillämme ei ole ollut ystävyyttä
enempää.
— No, joutavia, Boris Andrejitsh, — puheli, vuorostaan Pietari
Vasiljitsh: — Kuinka sivistyneenä maailmanmiehenä voitte olla ystävä
vaatimattoman maalaistytön kanssa?
— Taas te sitä samaa! — Keskeytti toistamiseen Boris Andrejitsh.
—
Miksi te sekoitatte sivistystä tähän asiaan? Sitä minä en ymmärrä?
Boris Andrejitsh hieman suuttui.
— Mutta kuulkaa, — jatkoi Pietari Vasiljitsh kärsimättömästi, jos se
on sopimatonta, tahdon vaan sanoa, että teillä kyllä on oikeus salata
minulta mitä tahdotte, mutta jos aiotte pettää, sanon: minua ette
petä. Onhan minullakin silmät. Eilinen päivä (he olivat olleet yhdessä
Stepan Petrovitshin luona) paljasti minulle paljon…
— Mutta, mitä se paljasti juuri teille.
— Sen se minulle paljasti, että te rakastatte häntä. Olettepa
mustankipeäkin hänen tähtensä.
Vjasovnin vilkasi Pietari Vasiljitshiin.
— No, mutta rakastaako hän minua?

— Sitä en osaa sanoa, mutta olisipa kumma, jos hän ei teitä
rakastaisi.
— Sentähden, että olen sivistynyt, aioitte kait sanoa?
— Sentähden, ja sentähden, että teillä on hyvä taloudellinen
asema. No, ja teidän ulkomuotonne on myös miellyttävä. Mutta
pääasia on — varallisuus.
Vjasovnin nousi ja meni ikkunan luo.
— Mistä te päätätte, että olin mustasukkainen? — kysyi hän äkkiä
kääntyen Pietari Vasiljitsh päin.
— Siitä, että te eilen ette olleet tapaisenne, ennenkuin tuo
tyhjäntoimittaja Karantjev oli matkustanut tiehensä.
Vjasovnin ei vastannut mitään, mutta tunsi ystävänsä puhuvan
totta. Tämä Karantjev oli huoleton ylioppilas, iloinen kaunosielu, ei
älytön, mutta toivottomuuteen vajonnut, sortunut. Intohimot olivat
jo nuorena jäytäneet hänen voimansa, hän jäi liian varhain hoivaa
vaille. Hänellä oli mustalaisen hurjat kasvot, ja muutenkin hän oli
mustalaisen näköinen, lauloi ja tanssi kuin mustalainen. Hän rakastui
kaikkiin naisiin. Veerotshka miellytti häntä suuresti. Boris Andrejitsh
tutustui häneen Barsukovin luona ja aluksi mieltyi häneen; mutta
huomattuaan millä kasvojenilmeillä Veerotshka kuunteli häntä,
alkoivat hänen ajatuksensa Karantjevista muuttua.
— Pietari Vasiljitsh, — sanoi Boris Andrejitsh, lähestyessään
ystäväänsä ja asettuen seisomaan hänen eteensä: — minun täytyy
tunnustaa, minusta tuntuu kuin olisitte oikeassa. Olen kyllä sellaista
kauankin tuntenut, mutta te avasitte lopullisesti silmäni. Minä en,

tosiaankaan, ole välinpitämätön Veerotshkasta; mutta mitäpä siitä
sitten. Kuulkaahan, Pietari Vasiljitsh, emmehän kumpikaan, ei hän
enkä minä, halua mitään kunniatonta, sitä paitsi, sanoinhan sen jo
teille, en ole huomannut hänen puoleltaan mitään
myötätuntoisuuden oireita minua kohtaan.
— Yhä samaa, — vastasi Pietari Vasiljitsh: — viekkaudessa väkevä.
Boris Andrejitsh vaikeni.
— Mitä minun on tehtävä, Pietari Vasiljitsh?
— Mitäkö? Lakata kulkemasta.
— Niinkö arvelette?
— Tietysti… Ettehän aio naida häntä! Vjasovnin vaikeni taaskin.
— Niin, miksi ei voisi vaikkapa naidakin? — huudahti hän vihdoin.
— Siksi, Boris Andrejitsh, johan sen sanoin: hän ei ole teidän
vertaisenne.
— Sitä en saata huomata.
— Mutta, jos ette näe, niin tehkää kuin tahdotte. Sittepähän
näette.
Minä en ole teidän holhoojanne.
Ja Pietari Vasiljitsh alkoi täyttää piippuaan. Boris Andrejitsh istui
ikkunan luo ja vaipui ajatuksiinsa.
Pietari Vasiljitsh ei häirinnyt häntä, vaan rauhallisesti puhalteli
savupilviä ilmaan. Vihdoin Boris Andrejitsh nousi ja tavallista

kiihtyneempänä käski valjastamaan hevoset.
— Mihin sinä nyt? — kysyi Pietari Vasiljitsh.
— Barsukoviin, — vastasi Boris Andrejitsh lyhyesti.
Pietari Vasiljitsh hämmästyi.
— Tulenko mukaan, vai kuinka?
— Ei, Pietari Vasiljitsh; tahtoisin tänään lähteä yksin. Tahdon
selvittää välini Veeran kanssa.
— Kuten tahdotte.
— Kas niin, — sanoi hän itselleen, saatettuaan Boris Andrejitshin
ovelle, — kuten sanottu, leikistä tuli tosi… Mutta kaikki on sulaa
hullutusta, — lisäsi hän, asettuen mukavasti sohvalle.
Saman päivän iltana Pietari Vasiljitsh odottamatta ystävänsä
palaamista oli juuri rupeamaisillaan makuulle, kun ovi yht'äkkiä
aukeni ja huoneeseen syöksyi lumisena Boris Andrejitsh heittäytyen
ystävänsä kaulaan.
— Ystäväni, Pietari Vasiljitsh, onnittele minua! — huudahti hän,
sinutellen ystäväänsä ensi kertaa: — hän on suostunut ja ukko
myöskin… Kaikki on jo suoritettu!
— Kuinka, mitä? — mörähti hämmästyneenä Pietari Vasiljitsh.
— Minä menen naimisiin!
— Veerotshkan kanssa.

— Hänen… Kaikki on päätetty ja sovittu.
— Se on mahdotonta!
— No, mikä mies sinä olet!… Et usko, kun selvästi sanotaan.
Pietari Vasiljitsh pani kiireesti tohvelit paljaaseen jalkaansa, heitti
hartioilleen viitan ja huudahti:
— Makedonia, teetä! — lisäten: — Koska asia jo on päätetty, ei se
enää puhumisesta parane. Antakoon Jumala teille onnea ja
menestystä! Mutta kerro minulle, ole hyvä, kuinka se tapahtui?
Ja juuri siitä hetkestä aikain molemmat ystävät alkoivat sinutella
toisiaan, mikä ei milloinkaan ennen ollut tapahtunut.
— Aivan mielelläni, — vastasi Vjasovnin ja alkoi kertoa.
Ja todellakin, katsokaamme, kuinka kaikki tämä tapahtui.
Kun Boris Andrejitsh tuli Stepan Petrovitshin luo, ei tämän luona,
vastoin tavallisuutta, ollut ainoatakaan vierasta, eikä hän itse
kulkenut edestakaisin, vaan istui voltaire-tuolissaan: hän voi pahoin.
Hän ei puhunut senvuoksi sanaakaan, mutta nyökkäsi ystävällisesti
päätään Vjasovninille, kun tämä astui huoneeseen, osoitti pöytää,
jolla oli viinaa ja sakuskaa, sitten Veeraa ja sulki silmänsä. Vjasovnin
ei muuta halunnutkaan; hän istui Veerotshkan luo ja alkoi hänen
kanssaan puoliääneen puhella. Puhuivat Stepan Petrovitshin
terveydestä.
— Minua aina kammoksuttaa, kun hän tulee pahoinvoivaksi, —
sanoi Veerotshka. Hän on sellainen: ei valita, ei pyydä mitään, ei
sanaakaan sano. Ei sano, vaikka tuntee sairastuvansa.

— Ja te rakastatte häntä suuresti? — kysyi Vjasovnin.
— Ketä? Isääkö? Niin, yli kaiken koko maailmassa. Jumala
varjelkoon, jos hänelle jotain tapahtuisi. Minä, varmaankin, kuolisin.
— Siis, ette voi mitenkään hänestä erota?
— Erota? Miksi erota?
Boris Andrejitsh katsoi häneen.
— Neitonen ei saa koko ikäänsä elää vanhempainsa talossa.
— Kah! Mikä teille nyt pälkähti päähän… No, siihen nähden voin
olla levollinen… Kuka minusta huolisi?…
— "Minä!" oli Boris Andrejitsh vähällä vastata, mutta hillitsi
kielensä.
— Mitä te nyt kävitte noin miettimään? — kysyi hän katsoen Boris
Andrejitshiin lempeästi hymyillen, kuten tavallisesti.
— Minä mietin, — vastasi hän, minä mietin… että… — Mutta sitten
hän yht'äkkiä muutti äänensä ja kysyi, oliko Veera kauan ollut tuttu
Karantjevin kanssa.
— Minä en todellakaan muista… Niitä on aina kulkenut niin paljon
isän luona. Muistaakseni hän tuli meille ensi kerran viime vuonna.
— Sanokaa: pidättekö hänestä?
— En, — vastasi Veerotshka mietittyään hetkisen.
— Miksi ei?

— Hän on niin likainen, — vastasi Veera suoraan. — Muuten hän
kyllä saattaa olla hyvä ihminen, ja laulaa kauniisti… sydän ihan
lämpenee, kun hän laulaa.
— Niinkö? sanoi Vjasovnin ja, vaiettuaan hetken lisäsi: — kenestä
te sitten pidätte?
— Monestakin, — esimerkiksi teistä.
— Mehän olemmekin ystäviä, sehän on tunnettu asia. Mutta
ettekö pidä kestään enemmän kuin minusta.
— Kylläpä te olette utelias.
— Mutta te olette kovin kylmä.
— Kuinka niin? kysyi Veerotshka, naivisti.
— Kuulkaa… — alkoi Vjasovnin sanoa. Mutta samassa Stepan
Petrovitsh kääntyi, nojatuolissaan.
— Kuulkaa, — jatkoi hän tuskin kuuluvasti, ja tunsi valtimon
tykyttävän: — minulla on teille jotain hyvin tärkeää sanottavana…
mutta ei täällä.
— Missä sitten?
— Vaikkapa viereisessä huoneessa.
— Mitä kummia? — kysyi Veerotshka: — varmaankin joku
salaisuus.
— Niin, salaisuus.

— Salaisuusko, — ihmetteli Veerotshka uudelleen ja läksi
viereiseen huoneeseen.
Vjasovnin seurasi häntä kuin kuumeessa.
— No, mitä sitten? — kysyi Veera uteliaana.
Boris Andrejitsh olisi tahtonut puhua asiaa etäältä; mutta kun hän
katsoi noihin nuoriin kasvoihin, joilla väikkyi tuttu, rakas hymyily, kun
hän katsoi noihin kirkkaisiin silmiin, joista häntä kohtasi lempeä,
suora hyvyys, ei hän osannut muuta kuin aivan koruttomasti kysyä:
— Veera Stepanova, tahdotteko tulla vaimokseni?
— Mitä? — kysyi Veerotshka, kuin säikähtyen ja punastui korviaan
myöten.
— Tahdotteko te tulla minun vaimokseni? — toisti Vjasovnin
konemaisesti.
— Minäkö… minä, en tiedä todellakaan, en odottanut… se tuli
niin… — tapaili Veera, etsien tukea ikkunanlaudasta, sillä hän tunsi
kuin kaatuvansa, — sitten hän yht'äkkiä syöksyi ulos ja kiiruhti
omaan makuusuojaansa.
Boris Andrejitsh seisoi hetken aikaa paikallaan ja kokonaan
hämillään palasi takaisin huoneeseensa. Pöydällä oli numero
"Moskovan sanomia". Hän otti sen ja istui katselemaan sen rivejä
vähääkään ajattelematta mitä luki ja ymmärtämättä, mitä hänelle oli
tapahtunut. Neljännestunti kului häneltä siinä mielentilassa. Mutta
sitten kuului takaa kevyttä kahinaa, ja katsomatta taakseen hän
tunsi Veeran lähestyvän.

Kului vielä hetkinen. Hän katsoi hieman syrjään lehdestään. Veera
istui akkunan luona selin, hän näytti kalpealta. Viimein Boris
Andrejitsh rohkaisi mielensä, nousi, meni hänen luoksensa ja istui
tuolille hänen vierelleen…
Stepan Petrovitsh istui liikkumatta nojatuolissaan pää selkäimen
varassa.
— Suokaa anteeksi, Veera Stepanova, — alkoi Vjasovnin hieman
vaivalloisesti, — tein väärin alkaissani niin odottamatta… ja sitäpaitsi
— aiheettomasti…
Veerotshka ei vastannut mitään.
— Mutta kun se nyt kerran niin tapahtui, — jatkoi Boris Andrejitsh:
— niin tahtoisin tietää minkä vastauksen…
Veera loi silmänsä alas; hänen poskensa punottivat.
— Veera Stepanova, yksi sana.
— Minä, todellakaan, en tiedä, — alkoi hän: Boris Andrejitsh… Se
riippuu isästä…
— Etkö ole terve? — kuului äkkiä Stepan Petrovitshin ääni.
Veerotshka vavahti ja nosti äkkiä päänsä. Stepan Petrovitshin
silmät alkoivat tuijottaa ja ilmaista levottomuutta. Veera meni hänen
luokseen.
— Te kysyitte jotain minulta, isä? Stepan Petrovitsh katsoi häneen
tiukasti.
— Olethan terve? — kysyi hän vielä kerran.

— Tietysti, kuinka te voitte?
— Brau, brau, — puhui hän hiljaa sulkien taas silmänsä.
Veerotshka lähti ovelle päin, Boris Andrejitsh pidätti hänet.
— Sanokaa minulle ainakin, saanko puhua isänne kanssa?
— Kuten suvaitsette, — kuiskasi hän: — mutta, Boris Andrejitsh,
minusta tuntuu, etten ole teidän vertaisenne.
Boris Andrejitsh olisi tahtonut ottaa häntä kädestä; mutta hän
väisti ja meni ulos.
"Kummallista! — ajatteli hän: — hän haastaa aivan samaa kuin
Krupitsyn."
Jäätyään kahdenkesken Stepan Petrovitshin kanssa, Boris
Andrejitsh päätti vakaasti keskustella hänen kanssaan
äänekkäämmin, ja, mahdollisuuden mukaan, valmistaa häntä
odottamattomaan ehdotukseensa; mutta aikeen toteuttaminen näytti
tällä kertaa vaikeammalta, kuin Veeran kanssa. Stepan Petrovitsh oli
hiukan kuumeessa. Hän näytti milloin vaipuvan mietteisiinsä milloin
uinailevan, ja epämielellään vastasi kysymyksiin ja huomautuksiin,
joiden avulla Boris Andrejitsh toivoi kauttarantain pääsevänsä
keskustelun ydinkysymykseen… Toisin sanoen, kun Boris Andrejitsh
huomasi että kaikki hänen yrityksensä raukenevat tyhjiin, päätti hän
käydä suoraan asiaan.
Muutaman kerran hän kokosi voimansa, valmistautuakseen
puhumaan, mutta pysähtyi, eikä saanut sanaakaan sanotuksi.

— Stepan Petrovitsh, — alkoi hän vihdoin: — aion tehdä teille
ehdotuksen, joka tulee suuresti teitä hämmästyttämään.
— Brau, brau, — sanoi Stepan Petrovitsh rauhallisesti.
— Sellaisen ehdotuksen, joka on teille aivan odottamaton.
Stepan Petrovitsh aukasi silmänsä.
— Mutta älkää vaan suuttuko minuun, pyydän…
Stepan Petrovitshin silmät aukenivat vielä suuremmiksi.
— Minä… minä aion pyytää teidän tyttärenne, Veera Stepanovnan
kättä…
Stepan Petrovitsh kohosi voltaire-tuolissaan korkeammalle…
— Mitä? kysyi hänkin ja hänen kasvonsa saivat aivan saman
ilmeen kuin Veeran äsken.
Boris Andrejitshin oli pakko uudistaa esityksensä.
Stepan Petrovitsh kiinnitti silmänsä Vjasovniniin ja katseli häntä
kauan ääneti, niin että Vjasovninista lopulta alkoi tuntua tukalalta.
— Tietääkö Veera? — kysäsi Stepan Petrovitsh.
— Minä puhuin asian Veera Stepanovnalle, ja hän salli minun
kääntyä teidän puoleenne.
— Juuri äskenkö puhuitte?
— Niin, juuri nyt.

— Odottakaa, — pyysi Stepan Petrovitsh ja meni ulos.
Boris Andrejitsh jäi yksin ukon huoneeseen. Jäykistyneenä katsoi
hän milloin seiniin, milloin lattiaan, kunnes vihdoin kuului
kavionkopsetta ulkoa, portaiden luota, eteisen oveen kolkutettiin, ja
jykeä ääni kysyi: "Kotonako?" Kuului askeleita, ja huoneeseen astui
tuttavamme Mihiej Mihieitsh.
Boris Andrejitsh oli aivan pyörtyä harmista.
— Kylläpä täällä on kuuma! — huudahti Mihiej Mihieitsh ja istua
mäiskäytti sohvaan. - Ahaa, päivää! Mutta missä on Stepan
Petrovitsh?
— Hän meni ulos, kohta tulee.
— Kova pakkanen tänään, — huomautti Mihiej Mihieitsh, ja kaasi
viinaa lasiin. Minä tulen taaskin kaupungista.
— Kaupungistako? — vastasi Vjasovnin, vaivoin hilliten
mielenkuohuaan.
— Kaupungista tietysti, — toisti Mihiej Mihieitsh: — ja yhä saman
roiston, Onufreij'in tähden. Voitteko ajatella? Sanon teille sen, hän
on roisto, roisto joka tapauksessa. Ei tässä jouda muuta kuin
kuleksimaan hänen kanssaan maita mantereita. En tosiaan ymmärrä,
mitä poliisi odottaa. Viimein saa hänen tähtensä kulkea maailman
ympäri, Jumala nähköön!
Stepan Petrovitsh tuli huoneeseen.
Mihiej Mihieitsh alkoi kertoa hänelle retkistään Onufreij'n kanssa.

— Miks'ei kukaan kurista häntä, — huudahti hän.
— Kuristako, — matki Stepan Petrovitsh ja oli aivan menehtyä
nauruunsa.
Mihiej Mihieitshiäkin alkoi naurattaa katsellessaan Stepan
Petrovitshiä, ja hän sanoi toistamiseen: "tosiaankin, hänet sietäisi
kuristaa hengiltä", mutta kun Stepan Petrovitsh viimein kellistyi
sohvalle suonenvetoiseen naurunkohtaukseen, niin Mihiej Mihieitsh
kääntyi Boris Andrejitshiin ja sanoi levitellen käsiään:
— Katsokaas, hän on aina sellainen: naurahtaa yht'äkkiä, mille,
sen tietää Jumala. Sellainen on hänen julkea tapansa.
Veerotshka tuli huoneeseen kuin ahdistettuna, silmät punaisina.
— Isä ei ole tänään oikein terve, — huomautti hän puoliääneen
Mihiej Mihieitshille.
Mihiej Mihieitsh nyökkäsi päällään ja pani suuhunsa palasen
juustoa. Lopulta Stepan Petrovitsh vaikeni, nousi huokaisten ja alkoi
kävellä huoneessa edestakaisin. Boris Andrejitsh väitteli hänen
katseitaan ja istui kuin neuloilla. Mihiej Mihieitsh alkoi taas panetella
Onufrij Ilitshiä.
Istuttiin pöytään. Pöydässäkin oli Mihiej Mihieitsh koko ajan yksin
äänessä. Vihdoin, kun ilta jo alkoi käydä myöhäiseksi, otti Stepan
Petrovitsh Boris Andrejitshiä kädestä ja vei hänet vaieten toiseen
huoneeseen.
— Oletteko te hyvä ihminen? — kysyi hän, katsoen häntä silmiin.

— Olen rehellinen ihminen, Stepan Petrovitsh, — vastasi Boris
Andrejitsh: — sen voin vannoa, — ja rakastan teidän tytärtänne.
— Rakastatteko? oikeinko?
— Rakastan ja tahdon ansaita hänen rakkautensa.
— Etteköhän kyllästy? — kysyi taaskin Stepan Petrovitsh.
— En milloinkaan!
Stepan Petrovitshin kasvoilla värähteli tuskallinen ilme, ne aivan
kuin kutistuivat kokoon.
— No, katsokaa… Jos rakastatte… niin suostun.
Boris Andrejitsh aikoi syleillä häntä, mutta hän sanoi:
— Myöhemmin… hyvä.
Hän kääntyi seinään päin. Boris saattoi huomata, että hän itki.
Stepan Petrovitsh hieroi silmiään, seisoen yhä selin, sitten hän
meni työhuoneeseensa Boris Andrejitshin ohi ja katsomatta häntä
kasvoihin, — puhui hymyten kuten tavallisesti:
— Olkaa hyvä, tänään ei enää tarvitse… huomenna… kaikki… mitä
tarvitaan…
— Hyvä, hyvä, — vastasi Boris Andrejitsh, ja, mennessään hänen
jälessään huoneeseen, vaihtoi ymmärtävän silmäyksen Veeran
kanssa.

Hän oli iloisten, mutta samalla sekavien tunteiden vallassa. Hän ei
malttanut enää viipyä kauan Stepan Petrovitshin luona, Mihiej
Mihieitshin seurassa; hänen täytyi välttämättä päästä lähtemään, —
ja sitä paitsi tunsi hän nyt tarvitsevansa Pietari Vasiljitshiä. Hän lähti,
luvattuaan seuraavana päivänä uudistaa käyntinsä. Hyvästellessään
Veerotshkan kanssa eteisessä hän suuteli hänen kättänsä. Veera
katsoi häntä silmiin.
— Hyvästi huomiseen, — sanoi Boris Andrejitsh.
— Hyvästi, — vastasi neitonen hiljaa.
— Arvaappas, Pietari Vasiljitsh, — puheli Boris Andrejitsh,
lopetettuaan kertomuksensa ja astuessaan edestakaisin hänen
makuusuojansa lattiaa: — mikä ajatus on pälkähtänyt päähäni:
minkä tähden nuori mies ei useinkaan mene naimisiin? Sentähden,
ett'ei hän tahdo orjuuttaa elämäänsä; hän ajattelee: mikäpä kiire
minulla on? vielähän tässä on aikaa, ehkä tulee parempiakin
tilaisuuksia; mutta asia päättyy, tavallisesti, joko niin, että hän tulee
liian vanhaksi, tai nai ensimäisen, jonka tapaa, se on kaikki seuraus
itserakkaudesta ja ylpeydestä. Jos Jumala on lähettänyt tiellesi
armaan ja hyvän neitosen, niin älä päästä tilaisuutta käsistäsi, vaan
tule onnelliseksi äläkä turhia oikuttele. Veerotshkaa parempaa
vaimoa en löydä; ja jos häneltä puuttuu jotain kasvatukseen nähden,
niin on minun asiani korjata se. Hän on hieman flegmaattinen
esiintymiseltään, mutta se ei ole onnettomuus — päinvastoin! Kas
siitä näet, miksi minä tein kiirettä. Sinähän minua yllytit naimaan. Ja
jos minä olen erehtynyt, — lisäsi hän, seisahtuen ja arveltuaan
hiukan, jatkoi: — onnettomuus ei ole suuri sittenkään! minun
elämästäni ei kuitenkaan enää mitään tule.

Pietari Vasiljitsh kuunteli ystäväänsä äänettömänä unohtamatta
särpiä lasistaan huonoa teetä, jota uuttera Makedonia oli parhaansa
mukaan keittänyt.
— Miksi istut tuppisuuna? — kysyi vihdoin Boris Andrejitsh,
seisahtuen hänen eteensä. — Enkö puhu totta? Vai mitä sanot?
— Olet jo asian esittänyt, — vastasi Pietari Vasiljitsh kangertaen:
— isä on antanut siunauksensa, tytär ei ole vastustanut, mitä siitä
siis enää maksaa puhua. Ehkäpä on kaikki onneksi. Nyt on aika
ajatella häitä, eikä viisastella; ja aamu on iltaa viisaampi… Puhutaan
huomenna, niinkuin asiat vaativat.
— Syleile minua, onnittele, — vastasi Boris Andrejitsh: — ka, mikä
oletkaan!
— Syleilenpä vielä syleiltyänikin, varsin kernaasti.
Ja Pietari Vasiljitsh syleili Boris Andrejitshiä.
— Antakoon Jumala sinulle kaikkea tämän maailman hyvyyttä!
Ystävät erosivat.
"Kaikki vaan sentähden, — sanoi Pietari Vasiljitsh itselleen ääneen
maattuaan jonkun aikaa vuoteellaan ja kääntyen toiselle kyljelle, —
kaikki tämä on vaan siitä, ettei jäänyt palvelemaan sotaväkeen! On
tottunut elämään oman päänsä mukaan mistään muusta
välittämättä."
* * * * *

Kuukauden kuluttua Vjasovnin ja Veerotshka menivät naimisiin.
Vjasovnin nimenomaan vaati, että häitä ei enää siirrettäisi. Pietari
Vasiljitsh oli hänen sulhaspoikanaan. Koko ensi kuun kuluessa
Vjasovnin joka päivä kävi Stepan Petrovitshiä tervehtimässä; hänen
ja Veerotshkan suhteessa ei tapahtunut mitään muutosta:
Veerotshka kävi ujommaksi hänen seurassaan, siinä kaikki. Hän toi
Veerotshkalle "Jurij Miloslavskij'n" ja itse luki hänelle muutamia
lukuja. Tämä Sjakoskinin romaani miellytti häntä; mutta lopetettuaan
sen hän ei pyytänyt toista. Karantjev kävi jonkun kerran katsomassa
Veerotshkaa, joka nyt oli toisen morsian, ja, täytyy tunnustaa, tuli
juoneena, katseli häntä aivan kuin olisi tahtonut jotain sanoa, mutta
jätti sanomatta. Häntä pyydettiin laulamaan ja hän lauloi erään
alakuloisen laulun, sitten vielä toisen reippaan, heitti kitaran
sohvalle, sanoi hyvästit kaikille, istui rekeen ja asettui suulleen
heinille maata alkaen itkeä uikuttaa, kunnes nukkui sikeään uneen.
Häitten edellisenä päivänä Veerotshka oli surullinen, ja Stepan
Petrovitshin mieli oli masentunut. Hän toivoi Boris Andrejitshin
suostuvan muuttamaan heille asumaan, mutta tämä ei maininnut
sanaakaan siitä, päinvastoin hän ehdotti, että Stepan Petrovitsh
asettuisi joksikin ajaksi hänen luokseen. Ukko kieltäytyi: hän oli
tottunut omaan huoneeseensa. Veerotshka lupasi käydä häntä
tervehtimässä ainakin kerran viikossa, johon lupaukseen vanhus
vastasi surullisesti: "brau brau!"
Ja niin Boris Andrejitsh alkoi elää naineena miehenä. Ensi aikoina
kaikki sujui mainiosti. Veerotshka, erinomaisena emäntänä pani koko
talon hyvään kuntoon. Boris Andrejitsh ihaili hänen tyyntä, mutta
huolellista toimeliaisuuttaan, rakasti katsella, kuinka selvästi ja
hellävaroen hän kaikkia kohteli ja opasteli. Hän kutsui Veerotshkaa
"pieneksi hollantilaisekseen" eikä väsynyt yhä uudelleen kertomasta

Pietari Vasiljitshille onnestaan Huomattakoon samalla, että Pietari
Vasiljitsh hääpäivästä alkain ei käynyt lainkaan niin usein Boris
Andrejitshin luona, kuin ennen, eikä istunut enää niin kauan kuin
ennen, vaikka Boris Andrejitsh, vastaanotti hänet aivan yhtä
ystävällisesti kuin nuorenamiehenä ja vaikka Veerotshka hänestä
paljon piti.
— Sinun elämäsi ei ole enää sama, — puheli hän Vjasovninille,
joka ystävällisesti nuhteli häntä aiheettomasta kylläytymisestä: —
sinä olet nainut, minä naimaton. Minä voin häiritä.
Ensimmältä Vjasovnin ei vastustanut häntä; mutta vähitellen hän
huomasi kotoisen elämänsä käyvän ikäväksi ilman Krupitsyniä. Boris
Andrejitsh ei syyttänyt siitä vaimoansa, sillä hänestä ei ollut mitään
vaivaa; päinvastoin, hän toisinaan sai kokonaan jäädä omiin
hoteisiinsa, jopa kului monta aamukautta perätysten niin, ett'ei
sanaakaan vaihdettu, vaikka Boris Andrejitsh lähettikin hänelle
alituiseen tyytyväisiä, helliä silmäyksiä, ja joka kerta kun Veerotshka
kulki hänen ohitsensa kevyttä, notkuvaa käyntiään, sieppasi kiinni ja
suuteli kättä saaden aina vastineeksi hellän hymyilyn. Tämä hymyily
oli sama, joka aina oli hänen rakkautensa uudeksi virittänyt; mutta
riittikö se yksin siihen?
Heidän välillään oli liian vähän yhteistä, ja hän alkoi sitä aavistaa
ja aprikoida.
"Ei siitä pääse mihinkään, minun vaimollani on kovin vähän
edellytyksiä", — arveli Boris Andrejitsh kerran itsekseen sohvalla
kädet ristissä istuessaan.
Nyt kaikuivat hänen sielussaan entistä selvemmin Veerotshkan
kosimispäivänä lausumat sanat: "Minä en ole teidän vertaisenne!"

Welcome to our website – the perfect destination for book lovers and
knowledge seekers. We believe that every book holds a new world,
offering opportunities for learning, discovery, and personal growth.
That’s why we are dedicated to bringing you a diverse collection of
books, ranging from classic literature and specialized publications to
self-development guides and children's books.
More than just a book-buying platform, we strive to be a bridge
connecting you with timeless cultural and intellectual values. With an
elegant, user-friendly interface and a smart search system, you can
quickly find the books that best suit your interests. Additionally,
our special promotions and home delivery services help you save time
and fully enjoy the joy of reading.
Join us on a journey of knowledge exploration, passion nurturing, and
personal growth every day!
ebookbell.com

Algebraic Graph Theory Morphisms Monoids And Matrices 1st Edition Ulrich Knauer

About This Presentation

Slide Content

Tags

Categories

Download

Quick Actions

Statistics

Related Slideshows

Algebraic Graph Theory Morphisms Monoids And Matrices 1st Edition Ulrich Knauer

About This Presentation

Slide Content

Slide 1

Slide 2

Slide 3

Slide 5

Slide 7

Slide 8

Slide 9

Slide 10

Slide 11

Slide 12

Slide 13

Slide 15

Slide 16

Slide 17

Slide 18

Slide 19

Slide 20

Slide 21

Slide 22

Slide 23

Slide 24

Slide 25

Slide 26

Slide 27

Slide 28

Slide 29

Slide 30

Slide 31

Slide 32

Slide 33

Slide 34

Slide 35

Slide 36

Slide 37

Slide 38

Slide 39

Slide 40

Slide 41

Slide 42

Slide 43

Slide 44

Slide 45

Slide 46

Slide 47

Slide 48

Slide 49

Slide 50

Slide 51

Slide 52

Slide 53

Slide 54

Slide 55

Slide 56

Slide 57

Slide 58

Slide 59

Slide 60

Slide 61

Slide 62

Slide 63

Slide 64

Slide 65

Slide 66

Slide 67

Slide 68

Slide 69

Slide 70

Slide 71

Slide 72

Slide 73

Slide 74

Slide 75

Slide 76

Slide 77

Slide 78

Slide 79

Tags