A Seminar on Graph Theory

Frank Harary

• Éditeur: Dover Publications
• Année: 2015
• ISBN:
  9780486805146
• Sujet: Mathematics
• Sous-sujet: Discrete Mathematics

Presented in 1962–63 by experts at University College, London, these lectures offer a variety of perspectives on graph theory. Although the opening chapters form a coherent body of graph theoretic concepts, this volume is not a text on the subject but rather an introduction to the extensive literature of graph theory. The seminar's topics are geared toward advanced undergraduate students of mathematics.
Lectures by this volume's editor, Frank Harary, include `Some Theorems and Concepts of Graph Theory,` `Topological Concepts in Graph Theory,` `Graphical Reconstruction,` and other introductory talks. A series of invited lectures follows, featuring presentations by other authorities on the faculty of University College as well as visiting scholars. These include `Extremal Problems in Graph Theory` by Paul Erdös, `Complete Bipartite Graphs: Decomposition into Planar Subgraphs,` by Lowell W. Beineke, `Graphs and Composite Games,` by Cedric A. B. Smith, and several others.

[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 K_p 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 v₁, x₁, v₂, x₂, v₃ · · ·, v_n is said to join v₁ with v_n. 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 v₁, x₁, v₂, x₂, · · ·,v_n is often written v₁v₂· · ·v_n, the lines being evident by context. A cycle is a closed walk v₁v₂· · ·v_nv₁, n ≥ 3, in which the n points v_i 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 v₁v₂v₃v₄. is a path; in fact, it is a spanning path. The cycle v₁v₂v₄v₁ has length 3, and v₂v₁v₄v₂v₃v_A, 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...