The Theory of Graphs Book

	Introduction	vii
1	General Definitions
	Sets and Multivalued Functions	1
	Paths and Circuits of a Graph	5
	Chains and Cycles of a Graph	8
2	Descendance Relations
	Weak Ordering Associated with a Graph	11
	Inductive Graphs and Bases	13
3	The Ordinal Function and the Grundy Function on an Infinite Graph
	General Remarks Concerning Infinite Graphs	16
	Ordinal Function	19
	Grundy Functions	22
	Operations over Graphs	23
4	The Fundamental Numbers of the Theory of Graphs
	Cyclomatic Number	27
	Chromatic Number	30
	Methods for Finding the Chromatic Number	33
	Coefficient of Internal Stability	35
	Coefficient of External Stability	40
5	Kernels of a Graph
	Existence and Uniqueness Theorems	45
	Application to Grundy Functions	50
6	Games on a Graph
	Nim Type Games	52
	The General Definition of a Game (with Perfect Information)	58
	Strategies	60
7	The Problem of the Shortest Route
	Stepwise Procedures	65
	Various Generalizations	68
8	Transport Networks
	The Problem of Maximum Flow	71
	The Problem of Minimum Flow	77
	Problems of Flow when a Set of Values is Associated with each Arc	77
	Infinite Transport Networks	84
9	The Theorem of the Demi-Degrees
	Inward or Outward Demi-Degree	86
10	Matching of a Simple Graph
	The Maximum Matching Problem	92
	Deficiency of a Simple Graph	96
	The Hungarian Method	99
	Extensions to the Infinite Case	102
	Application to the Theory of Matrices	105
11	Factors
	Hamiltonian Paths and Circuits	107
	Factors and Methods for Determining Them	111
	The Problem of Finding a Partial Graph with Given Demi-Degrees	117
12	Centres of a Graph
	Centres	119
	Radius	120
13	The Diameter of a Strongly Connected Graph
	General Remarks on Strongly Connected Graphs without Loops	123
	Diameter	126
14	The Matrix Associated with a Graph
	The Use of Standard Matrix Operations	130
	Problems of Enumeration	132
	The Problem of the Leader	135
	The Use of Boolean Operations	138
15	Incidence Matrices
	Matrices with the Unimodular Property	141
	Systems with the Unimodular Property	146
	Cyclomatic Matrices	149
16	Trees and Arborescences
	Trees	152
	Analytic Treatment	156
	Arborescences	160
17	Euler's Problem
	Eulerian Cycles	165
	Eulerian Circuits	167
18	Matching in the General Case
	The Theory of Alternating Chains	171
	The Determination of a Partial Graph with Given Degrees	174
	Perfect Matching	178
	Application to the Coefficient of Internal Stability	184
19	Semi-Factors
	Hamiltonian Cycles and Semi-Factors	187
	A Necessary and Sufficient Condition for the Existence of a Semi-Factor	192
20	The Connectivity of a Graph
	Articulation Points	196
	Biconnected Graphs	198
	h-Connected Graphs	203
21	Planar Graphs
	General Properties	207
	Generalization	218
Appendix 1	Note on the General Theory of Games	220
Appendix 2	Note on Transport Problems	227
	Bibliography	238
	List of Symbols	245
	Index of Terms Used	246