Graph theory has experienced a tremendous growth during the 20thcentury. One of the main reasons for this phenomenon is theapplicability of graph theory in other disciplines such as physics,chemistry, psychology, sociology, and theoretical computer science.This book aims to provide a solid background in the basic topics ofgraph theory. It covers Dirac's theorem on k-connected graphs,Harary-Nashwilliam's theorem on the hamiltonicity of line graphs,Toida-McKee's characterization of Eulerian graphs, the Tutte matrixof a graph, Foumier's proof of Kuratowski's theorem on planar graphs,the proof of the nonhamiltonicity of the Tutte graph on 46 verticesand a concrete application of triangulated graphs. The book does notpresuppose deep knowledge of any'branch of mathematics, butrequires only the basics of mathematics. It can be used in an advancedundergraduate course ora beginning graduate course in graph theory.

Preface

Ⅰ Basic Results

 1.0 Introduction

 1.1 Basic Concepts

 t.2 Subgraphs

 1.3 Degrees of Vertices

 1.4 Paths and Connectedness

 1.5 Automorphism of a Simple Graph

 1.6 Line Graphs

 1.7 Operations on Graphs

 1.8 An Application to Chemistry

 1.9 Miscellaneous Exercises

 Notes

Ⅱ Directed Graphs

 2.0 Introduction

 2.1 Basic Concepts

 2.2 Tournaments

 2.3 k-Partite Tournaments

 Notes

Ⅲ Connectivity

 3.0 Introduction

 3.1 Vertex Cuts and Edge Cuts

 3.2 Connectivity and Edge-Connectivity

 3.3 Blocks

 3.4 Cyclical Edge-Connectivity of a Graph

 3.5 Menger's Theorem

 3.6 Exercises

 Notes

Ⅳ Trees

 4.0 Introduction

 4.1 Definition, Characterization, and Simple Properties

 4.2 Centers and Centroids

 4.3 Counting the Number of Spanning Trees

 4.4 Cayley's Formula

 4.5 Helly Property

 4.6 Exercises

 Notes

Ⅴ Independent Sets and Matehings

 5.0 Introduction

 5.1 Vertex Independent Sets and Vertex Coverings

 5.2 Edge-Independent Sets

 5.3 Matchings and Factors

 5.4 Matchings in Bipartite Graphs

 5.5* Perfect Matchings and the Tutte Matrix

 Notes

Ⅵ Eulerian and Hamiltonian Graphs

 6.0 Introduction

 6.1 Eulerian Graphs

 6.2 Hamiltonian Graphs

 6.3* Pancyclic Graphs

 6.4 Hamilton Cycles in Line Graphs

 6.5 2-Factorable Graphs

 6.6 Exercises

 Notes

Ⅶ Graph Colorings

 7.0 Introduction

 7.1 Vertex Colorings

 7.2 Critical Graphs

 7.3 Triangle-Free Graphs

 7.4 Edge Colorings of Graphs

 7.5 Snarks

 7.6 Kirkman's Schoolgirls Problem

 7.7 Chromatic Polynomials

 Notes

Ⅷ Planarity

 8.0 Introduction

 8.1 Planar and Nonplanar Graphs

 8.2 Euler Formula and Its Consequences

 8.3 Ks and K3.3 are Nonplanar Graphs

 8.4 Dual of a Plane Graph

 8.5 The Four-Color Theorem and the Heawood Five-Color Theorem

 8.6 Kuratowski's Theorem

 8.7 Hamiltonian Plane Graphs

 8.8 Tait Coloring

 Notes

Ⅸ Triangulated Graphs

 9.0 Introduction

 9.1 Perfect Graphs

 9.2 Triangulated Graphs

 9.3 Interval Graphs

 9.4 Bipartite Graph B（G） of a Graph G

 9.5 Circular Arc Graphs

 9.6 Exercises

 9.7 Phasing of Traffic Lights at a Road Junction

 Notes

Ⅹ Applications

 10.0 Introduction

 10.1 The Connector Problem

 10.2 Kruskal's Algorithm

 10.3 Prim's Algorithm

 10.4 Shortest-Path Problems

 10.5 Timetable Problem

 10.6 Application to Social Psychology

 10.7 Exercises

 Notes

List of Symbols

References

Index