## Introduction to graph theoryGraph Theory has recently emerged as a subject in its own right, as well as being an important mathematical tool in such diverse subjects as operational research, chemistry, sociology and genetics. Robin Wilson's book has been widely used as a text for undergraduate courses in mathematics, computer science and economics, and as a readable introduction to the subject for non-mathematicians. The opening chapters provide a basic foundation course, containing such topics as trees, algorithms, Eulerian and Hamiltonian graphs, planar graphs and colouring, with special reference to the four-colour theorem. Following these, there are two chapters on directed graphs and transversal theory, relating these areas to such subjects as Markov chains and network flows. Finally, there is a chapter on matroid theory, which is used to consolidate some of the material from earlier chapters. For this new edition, the text has been completely revised, and there is a full range of exercises of varying difficulty. There is new material on algorithms, tree-searches, and graph-theoretical puzzles. Full solutions are provided for many of the exercises. Robin Wilson is Dean and Director of Studies in the Faculty of Mathematics and Computing at the Open University. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Definitions and examples | 8 |

Paths and cycles | 26 |

Trees | 43 |

Copyright | |

7 other sections not shown

### Common terms and phrases

abstract dual adjacent algorithm Chapter chromatic index chromatic number chromatic polynomial colour complete bipartite graph complete graph component connected graph Corollary corresponding countable cube cutset of G cycle graph cycle matroid Deduce define denoted digraph edge in common edges joining edges of G elements Euler's formula Eulerian graph Eulerian trail Exercise genus geometric dual given graph G graph in Fig graph theory Hall's theorem Hamiltonian graph incident independent sets induction infinite graph isomorphic labelled tree least Let G Markov chain matrix maximum flow minimum number multiple edges non-planar Note null graph number of edges number of vertices partial transversal Petersen graph PG(k planar graph problem proof prove regular of degree Section set of edges shortest path shown in Fig simple graph simple planar graph spanning forest spanning tree strongly connected subsets tournament transversal matroid transversal theory vertex set vertices of degree vertices of G vw-disconnecting set