Introduction To Graph Theory: With Solutions To Selected Problems

✍ Scribed by Khee-meng Koh, Fengming Dong, Eng Guan Tay

• Publisher: WSPC
• Year: 2023
• Tongue: English
• Leaves: 309
• Category: Library

✦ Synopsis

Graph theory is an area in discrete mathematics which studies configurations (called graphs) involving a set of vertices interconnected by edges. This book is intended as a general introduction to graph theory. The book builds on the verity that graph theory even at high school level is a subject that lends itself well to the development of mathematical reasoning and proof. This is an updated edition of two books already published with World Scientific, i.e., Introduction to Graph Theory: H3 Mathematics & Introduction to Graph Theory: Solutions Manual. The new edition includes solutions and hints to selected problems. This combination allows the book to be used as a textbook for undergraduate students. Professors can select unanswered problems for tutorials while students have solutions for reference.

✦ Table of Contents

Contents
Preface
Notation
1. Fundamental Concepts and Basic Results
1.1 The Königsberg bridge problem
1.2 Multigraphs and graphs
1.3 Vertex degrees
1.3.1 The Handshaking Lemma
1.3.2 Regular graphs
Exercise 1.3
1.4 Paths, cycles and connectedness
1.4.1 Walks, trails, paths and cycles
1.4.2 Connected multigraphs
1.4.3 Distance
Exercise 1.4
2. Graph Isomorphisms, Subgraphs, the Complement of a Graph
2.1 Isomorphic graphs and isomorphisms
2.2 Testing isomorphic graphs
Exercise 2.2
2.3 Subgraphs of a graph
Exercise 2.3
2.4 The complement of a graph
Exercise 2.4
3. Bipartite Graphs and Trees
3.1 Bipartite graphs
Exercise 3.1
3.2 Trees
3.2.1 Special properties for trees
Exercise 3.2
3.3 Spanning trees of a graph
Exercise 3.3
4. Vertex-colourings of Graphs
4.1 The four-colour problem
4.2 Vertex-colourings and chromatic number
Exercise 4.2
4.3 Enumeration of chromatic number
Exercise 4.3
4.4 Greedy colouring algorithm
Exercise 4.4
4.5 An upper bound for the chromatic number and Brooks’ theorem
Exercise 4.5
4.6 Applications
Exercise 4.6
5. Matchings in Bipartite Graphs
5.1 Introduction
5.2 Matchings
Exercise 5.2
5.3 Hall’s theorem
Exercise 5.3
5.4 System of distinct representatives
Exercise 5.4
6. Eulerian Multigraphs and Hamiltonian Graphs
6.1 Eulerian multigraphs
Exercise 6.1
6.2 Characterization of Eulerian multigraphs
Exercise 6.2
6.3 Around the world and Hamiltonian graphs
6.4 A necessary condition for a graph to be Hamiltonian
Exercise 6.4
6.5 Two sufficient conditions for a graph to be Hamiltonian
Exercise 6.5
7. Digraphs and Tournaments
7.1 Digraphs
Exercise 7.1
7.2 Basic concepts
Exercise 7.2
7.3 Tournaments
Exercise 7.3
7.4 Two properties of tournaments
Exercise 7.4
8. Solutions of selected questions
8.1 Selected questions in Chapter 1
Exercise 1.2
Exercise 1.3
Exercise 1.4
8.2 Selected questions in Chapter 2
Exercise 2.2
Exercise 2.3
Exercise 2.4
8.3 Selected questions in Chapter 3
Exercise 3.1
Exercise 3.2
Exercise 3.3
8.4 Selected questions in Chapter 4
Exercise 4.3
Exercise 4.4
Exercise 4.5
Exercise 4.6
8.5 Selected questions in Chapter 5
Exercise 5.2
Exercise 5.3
Exercise 5.4
8.6 Selected questions in Chapter 6
Exercise 6.1
Exercise 6.2
Exercise 6.4
Exercise 6.5
8.7 Selected questions in Chapter 7
Exercise 7.1
Exercise 7.2
Exercise 7.3
Exercise 7.4
References
Books Recommended
Index