Pearls in Graph Theory

A Comprehensive Introduction

Nora Hartsfield, Gerhard Ringel

• Publisher: Dover Publications
• Year: 2013
• ISBN:
  9780486315522
• Topic: Matemáticas
• Subtopic: Matemáticas general

`Innovative introductory text . . . clear exposition of unusual and more advanced topics . . . Develops material to substantial level.` — American Mathematical Monthly
`Refreshingly different . . . an ideal training ground for the mathematical process of investigation, generalization, and conjecture leading to the discovery of proofs and counterexamples.` — American Mathematical Monthly
` . . . An excellent textbook for an undergraduate course.` — Australian Computer Journal
A stimulating view of mathematics that appeals to students as well as teachers, this undergraduate-level text is written in an informal style that does not sacrifice depth or challenge. Based on 20 years of teaching by the leading researcher in graph theory, it offers a solid foundation on the subject. This revised and augmented edition features new exercises, simplifications, and other improvements suggested by classroom users and reviewers. Topics include basic graph theory, colorings of graphs, circuits and cycles, labeling graphs, drawings of graphs, measurements of closeness to planarity, graphs on surfaces, and applications and algorithms. 1994 edition.

Chapter 1

BASIC GRAPH THEORY

1.1 Graphs and Degrees of Vertices

Before we give any definitions and theory, let us consider the following example. There is a basket containing an apple, a banana, a cherry and a date. Four children named Erica, Frank, Greg and Hank are each to be given a piece of the fruit. Erica likes cherries and dates; Frank likes apples and cherries; Greg likes bananas and cherries; and Hank likes apples, bananas, and dates. Figure 1.1.1 describes the situation. The problem is to give each child a piece of fruit that he or she likes. The reader is invited to find a solution. One can see the advantage of using Figure 1.1.1 as an aid to solving the problem.

Figure 1.1.1 is, in fact, an example of a graph. Another example with which we are all familiar is a road map. The map in Figure 1.1.2 is greatly simplified, of course. It shows some different ways of driving from San Jose to San Francisco.

Figure 1.1.1

Figure 1.1.2

Chemists use diagrams to picture molecules, and these diagrams are also graphs. Usually the hydrogen atoms are omitted from the diagrams by the chemists using shorthand structure, but the Kekulé structure includes them.

Figure 1.1.3. Water, H₂O.

Figure 1.1.4. Butane and isobutane, C₄H₁₀.

In Figures 1.1.6 and 1.1.7 the labels for carbon, hydrogen, and oxygen have been left out. See Figure 1.3.6 for another molecule C_60.

Graph theory is used in designing printed circuits for use in electronics devices. Circuits printed on silicon chips must be designed differently from those using insulated wires, since the conducting portions cannot cross one another. The graph of Figure 1.1.8 shows part of a printed circuit used in a computer.

Figure 1.1.5. Cyclohexane, C₆H_12.

Figure 1.1.6. Aspirin, C₉H₈O₄.

Figure 1.1.7. Vitamin A, C₂₀H₃₀O.

Algorithms can also be described by graphs. The graph of Figure 1.1.9 is a chart of the steps used in an algorithm for solving a certain problem using a computer.

Figure 1.1.8. Portion of a printed circuit

Figure 1.1.9

In the study of lattices and Boolean algebras, graphs arise as diagrams of these structures. Those who have studied set theory will recognize the diagrams of Figures 1.1.10 and 1.1.11 as lattices of subsets. For convenience, we use shorter notation for sets; for example, we write ABD for the set {A, B, D}. The diagrams of Figures 1.1.10 and 1.1.11 show all subsets of the set at the top. If one set is derived from another by deleting one element, then the two sets are connected by a line in the diagram.

Figure 1.1.10. The lattice of subsets of ABC.

Figure 1.1.11

The different factorizations of the integer 60 are shown in the diagram of Figure 1.1.12. Some more examples of graphs are shown in Figures 1.1.13, 1.1.14, 1.1.15, 1.1.16, and 1.1.17.

Figure 1.1....