IntroductiontoGraphTheory

INTRODUCTION TO GRAPH THEORY INTRODUCTION TO GRAPH THEORY Richard J. Trudeau DOVER PUBLICATIONS, INC. New York Copyright Copyright © 1993 by Richard J. Trudeau. Copyright © 1976 by the Kent State University Press. All rights reserved. Bibliographical Note This Dover edition, first published in 1993, is a slightly corrected, enlarged republication of the work first published by The Kent State University Press, Kent, Ohio, 1976. For this edition the author has added a new section, “Solutions to Selected Exercises,” and corrected a few typographical and graphical errors. Library of Congress Cataloging-in-Publication Data Trudeau, Richard J. Introduction to graph theory / Richard J. Trudeau. p. cm. Rev. ed. of: Dots and lines, 1976. Includes bibliographical references and index. ISBN-13: 978-0-486-67870-2 ISBN-10: 0-486-67870-9 1. Graph theory. I. Trudeau, Richard J. Dots and lines. II. Title. QA166.T74 1993 511'.5—dc20 93-32996 CIP Manufactured in the United States by Courier Corporation 67870908 www.doverpublications.com To Dick Barbieri and Chet Raymo TABLE OF CONTENTS Preface 1. PURE MATHEMATICS Introduction . . . Eu......