[1]
Some Theorems and Concepts of Graph Theory
The field of graph theory is even today being independently rediscovered by scholars in various disciplines as they require its techniques for the solution of their structural and combinatorial problems. In recent years, this subject has been receiving increasing attention and interest in mathematics and other sciences. The stimulus to the renaissance of graph theory stems from its wide applicability to many fields. In fact, the theory of graphs is now quite important not only in pure mathematics (combinatorial theory), but also in theoretical physics, electrical engineering, organic chemistry, social psychology, and operational research.
It is our hope that the presentation of some historical comments and illustrations, with the statements of selected theorems, will set the stage for the remaining lectures.
We will describe four independent approaches to graph theory:
(1) Euler: Kƶnigsberg Bridge Problem.
(2) Hamilton: Around the World.
(3) Cayley, Heawood: Four-color Conjecture.
(4) Kirchhoff, Cayley, Jordan, Sylvester: Trees.
Kƶnigsberg Bridge Problem
Euler (1707-1782) became the father of graph theory, as well as the rest of topology, when he settled a famous problem of his day called the Kƶnigsberg bridge problem [4]. The area in question contains two islands linked to each other and to the banks of the Pregel River by seven bridges, as in Fig. 1.1.
The problem was to begin at any of the four land areas and, without swimming or flying or travelling around the world, cross each bridge exactly once and return to the starting point. One can see immediately that there are many ways of attempting this problem without solving it.
The considerable contribution of Euler in this case was negative, for he proved that the problem is unsolvable. He replaced each land area by a point and each bridge by a line joining the corresponding points. The result, shown in Fig. 1.2, is a collection of points with lines joining them. The points, labeled a, b, c, and d, correspond to the land areas of Fig. 1.1.
Fig. 1.1. The Kƶnigsberg bridge problem.
Fig. 1.2. The āmultigraphā of the Kƶnigsberg bridge problem.
Fig. 1.3. A (4, 5) graph with points and lines labeled.
Since almost any two graph theorists use different terminology, and since we wish this exposition to be self-contained, we will preface a precise formulation of the problem with a rather substantial list of definitions.
A graph G consists of a finite nonempty set V of points and a set X of lines, each of which joins two distinct points. We assume that distinct lines do not join the same pair of points; otherwise, as in Fig. 1.2, the configuration is a multigraph. Furthermore, if we permit loops, that is, lines joining a point with itself, the result is a general graph. A (p, q) graph has p points and q lines. The number of points in a graph is called its order. Fig. 1.3 shows a (4, 5) graph with points and lines labeled, i.e., designated by symbols.
The two points joined by a line are adjacent, and each is incident with the line. Two graphs are isomorphic if there is a one-to-one correspondence between their sets of points preserving adjacency. The degree d(v) of a point v is the number of lines incident with it. A point of degree 0 is isolated, and the graph consisting of such a point is called trivial. In a regular graph all points have the same degree. A regular graph in which every point has degree 3 is called cubic. The complete graph Kp of order p has every pair of its points adjacent and so is regular of degree p ā 1. All the complete graphs with up to five points are shown in Fig. 1.4.
A walk in a graph G is an alternating sequence of points and lines of G, beginning and ending with a point, in which each line is incident with the point preceding it and the point following it. A walk of the form v1, x1, v2, x2, v3 Ā· Ā· Ā·, vn is said to join v1 with vn. The length of a walk is the number of occurrences of lines in it. A trail is a walk in which all lines are distinct. A path is a walk in which all points (and hence all lines) are distinct. A closed walk has the same first and last points. The walk v1, x1, v2, x2, Ā· Ā· Ā·,vn is often written v1v2Ā· Ā· Ā·vn, the lines being evident by context. A cycle is a closed walk v1v2Ā· Ā· Ā·vnv1, n ā„ 3, in which the n points vi are distinct. A spanning walk (spanning path, spanning cycle, and so on) contains all the points of G.
Some of these concepts are illustrated in Fig. 1.3. The walk v1v2v3v4. is a path; in fact, it is a spanning path. The cycle v1v2v4v1 has length 3, and v2v1v4v2v3vA, is a trail containing all lines.
In a connected graph, every pair of distinct points is joined by a path. A subgraph of G consists of subsets of V and X which themselves form a graph.
Fig. 1.4. The smallest complete graphs.
A component of G is a maximal connected subgraph. Ob...