Chapter 1 FUNDAMENTAL CONCEPTS 1
1．1 Graph definitions 1
1．2 Local degrees 7
1．3 Subgraphs 12
1．4 Binary relations 13
1．5 Incidence matrices 18
Chapter 2 CONNECTEDNESS 22
2．1 Sequences,paths and arcs 22
2．2 Connected components 23
2．3 One-to-one correspondences 25
2．4 Distances 27
2．5 Elongations 31
2．6 Matrices and paths．Product graphs 33
2．7 Puzzles 36
Chapter 3 PATH PROBLEMS 38
3．1 Euler paths 38
3．2 Euler paths in infinite graphs 42
3．3 An excursion into labyrinths 47
3．4 Hamilton circuits 52
Chapter 4 TREES 58
4．1 Properties of trees 58
4．2 Centers in trees 62
4．3 The circuit rank 67
4．4 Many-to-one correspondences 68
4．5 Arbitrarily traceable graphs 74
Chapter 5 LEAVES AND LOBES 78
5．1 Edges and vertices of attachment 78
5．2 Leaves 81
5．3 Homomorphic graph images 83
5．4 Lobes 85
5．5 Maximal circuits 89
Chapter 6 THE AXIOM OF CHOICE 92
6．1 Well-ordering 92
6．2 The maximal principles 94
6．3 Chain sum properties 96
6．4 Maximal exclusion graphs 100
6．5 Maximal trees 101
6．6 Interrelations between maximal graphs 103
Chapter 7 MATCHING THEOREMS 106
7．1 Bipartite graphs 106
7．2 Deficiencies 108
7．3 The matching theorems 110
7．4 Mutual matchings 113
7．5 Matchings in special graphs 117
7．6 Bipartite graphs with positive deficiencies 121
7．7 Applications to matrices 125
7．8 Alternating paths and maximal matchings 132
7．9 Separating sets 138
7．10 Simultaneous matchings 139
Chapter 8 DIRECTED GRAPHS 145
8．1 The inclusion relation and accessible sets 145
8．2 The homomorphism theorem 149
8．3 Transitive graphs and embedding in order relations 150
8．4 Basis graphs 152
8．5 Alternating paths 156
8．6 Subgraphs of first degree 159
Chapter 9 ACYCLIC GRAPHS 162
9．1 Basis graphs 162
9．2 Deformations of paths 163
9．3 Reproduction graphs 166
Chapter 10 PARTIAL ORDER 170
10．1 Graphs of partial order 170
10．2 Representations as sums of ordered sets 170
10．3 Lattices and lattice operations．Closure relations 175
10．4 Dimension in partial order 178
Chapter 11 BINARY RELATIONS AND GALOIS CORRESPONDENCES 183
11．1 Galois correspondences 183
11．2 Galois connections for binary relations 187
11．3 Alternating product relations 191
11．4 Ferrers relations 193
Chapter 12 CONNECTING PATHS 197
12．1 The cross-path theorem 197
12．2 Vertex separation 200
12．3 Edge separation 202
12．4 Deficiency 203
Chapter 13 DOMINATING SETS,COVERING SETS AND INDEPENDENT SETS 206
13．1 Dominating sets 206
13．2 Covering sets and covering graphs 208
13．3 Independent sets 210
13．4 The theorem of Turan 214
13．5 The theorem of Ramsey 216
13．6 A problem in information theory 220
Chapter 14 CHROMATIC GRAPHS 224
14．1 The chromatic number 224
14．2 Sums of chromatic graphs 227
14．3 Critical graphs 229
14．4 Coloration polynomials 234
Chapter 15 GROUPS AND GRAPHS 239
15．1 Groups of automorphisms 239
15．2 Cayley＇s color graphs for groups 242
15．3 Graphs with prescribed groups 244
15．4 Edge correspondences 245
BIBLIOGRAPHY 250
LIST OF CONCEPTS 265
INDEX OF NAMES 269