Graph Theory

Undergraduate Mathematics

Khee Meng Koh, Fengming Dong, Kah Loon Ng;Eng Guan Tay

• Publisher: WSPC
• Year: 2015
• ISBN:
  9789814641616
• Topic: Mathematics
• Subtopic: Discrete Mathematics
• Index: Mathematics

This book is an expansion of our first book Introduction to Graph Theory: H3 Mathematics. While the first book was intended for capable high school students and university freshmen, this version covers substantially more ground and is intended as a reference and textbook for undergraduate studies in Graph Theory. In fact, the topics cover a few modules in the Graph Theory taught at the National University of Singapore. The reader will be challenged and inspired by the material in the book, especially the variety and quality of the problems, which are derived from the authors' years of teaching and research experience.

Request Inspection Copy

Contents:

• Fundamental Concepts and Basic Results
• Graph Isomorphisms, Subgraphs, the Complement of a Graph and Graphic Sequences
• Bipartite Graphs and Trees
• Eulerian Multigraphs and The Chinese Postman Problem
• Hamiltonian Graphs and The Traveling Salesman Problem
• Connectivity
• Independence, Matching and Covering
• Vertex-colorings and Planar Graphs
• Domination
• Digraphs and Tournaments

Readership: Undergraduates in combinatorics and graph theory.
Key Features:

• The coverage includes some frontier research and this can encourage readers to engage in some research themselves
• The set of problems is extensive and some are cutting-edge
• Not intended for the average Joe in Mathematics

Chapter 1

Fundamental Concepts and Basic
Results

1.1The Königsberg Bridge Problem

The River Pregel flowed through the old city of Königsberg in 18^th century Eastern Prussia. Back then, there were seven bridges over the river connecting the two islands (B and D) and two opposite banks (A and C) as shown in Fig. 1.1.1.

Fig. 1.1.1

It was said that the people in the city had always amused themselves with the following problem:

Starting with any one of the four places A, B, C or D as shown in Fig. 1.1.1, is it possible to have a walk which passes through each of the seven bridges once and only once, and return to where you started?

No one could find such a walk; and after a number of tries, people believed that it was simply not possible, but no one could convincingly prove it either.

Leonhard Euler, the greatest mathematician that Switzerland has ever produced, was told of the problem. He noticed that the problem was very much different in nature from the problems in traditional geometry, and instead of considering the original problem, he studied its much more general version which encompassed any number of islands or banks, and any number of bridges connecting them. His finding was contained in the article Euler (1736). As a direct consequence of his finding, he deduced the impossibiity of having such a walk in the Königsberg bridge problem. This was historically the first time a proof was given from the mathematical point of view.

How did Euler generalize the Königsberg bridge problem? How did he solve his more general problem? What was his finding?

1.2Multigraphs and Graphs

Euler observed that the Königsberg bridge problem had nothing to do with traditional geometry where the measurements of lengths and angles, and relative locations of vertices count. How large the islands and banks are, how long the bridges are, and whether an island is at the south or north of a bank are immaterial. The key ingredients are whether the islands or banks are connected by a bridge, and by how many bridges.

Euler’s idea was essentially as follows: represent the islands or banks by ‘dots’, one for each island or bank, and two dots are joined by k ‘lines’ (not necessarily straight), where k ≥ 0, when and only when the respective islands or banks represented by the dots are connected by k bridges. Thus the situation for the Königsberg bridge problem is represented by the diagram in Fig. 1.2.1.

Fig. 1.2.1

The diagram in Fig. 1.2.1 is now known as a multigraph. Int...