Introduction to Graph Theory

by Trudeau, Richard J.

• ISBN13: 9780486678702
• ISBN10: 0486678709
• Format: Paperback
• Copyright: 1994-02-09
• Publisher: Dover Publications

Summary

A stimulating excursion into pure mathematics aimed at "the mathematically traumatized," but great fun for mathematical hobbyists and serious mathematicians as well. This book leads the reader from simple graphs through planar graphs, Euler's formula, Platonic graphs, coloring, the genus of a graph, Euler walks, Hamilton walks, more. Includes exercises. 1976 edition.

Table of Contents

Preface

Pure Mathematics

Introduction

Euclidean Geometry as Pure Mathematics

Games

Why Study Pure Mathematics?

What's Coming

Suggested Reading

Graphs

Introduction

Sets

Paradox

Graphs

Graph diagrams

Cautions

Common Graphs

Discovery

Complements and Subgraphs

Isomorphism

Recognizing Isomorphic Graphs

Semantics

The Number of Graphs Having a Given nu

Exercises

Suggested Reading

Planar Graphs

Introduction

UG, K subscript 5, and the Jordan Curve Theorem

Are there More Nonplanar Graphs?

Expansions

Kuratowski's Theorem

Determining Whether a Graph is Planar or Nonplanar

Exercises

Suggested Reading

Euler's Formula

Introduction

Mathematical Induction

Proof of Euler's Formula

Some Consequences of Euler's Formula

Algebraic Topology

Exercises

Suggested Reading

Platonic Graphs

Introduction

Proof of the Theorem

History

Exercises

Suggested Reading

Coloring

Chromatic Number

Coloring Planar Graphs

Proof of the Five Color Theorem

Coloring Maps

Exercises

Suggested Reading

The Genus of a Graph

Introduction

The Genus of a Graph

Euler's Second Formula

Some Consequences

Estimating the Genus of a Connected Graph; g-Platonic Graphs

The Heawood Coloring Theorem

Exercises

Suggested Reading

Euler Walks and Hamilton Walks

Introduction

Euler Walks

Hamilton Walks

Multigraphs

The Konigsberg Bridge Problem

Exercises

Suggested Reading

Afterword

Solutions to Selected Exercises

Index

Special symbols

Table of Contents provided by Publisher. All Rights Reserved.