Karin R Saoub - Graph Theory: An Introduction to Proofs, Algorithms, and Applications

Textbooks in Mathematics

Series editors:

Al Boggess, Kenneth H. Rosen

Real Analysis

With Proof Strategies

Daniel W. Cunningham

Train Your Brain

Challenging Yet Elementary Mathematics

Bogumil Kaminski, Pawel Pralat

Contemporary Abstract Algebra, Tenth Edition

Joseph A. Gallian

Geometry and Its Applications

Walter J. Meyer

Linear Algebra

What You Need to Know

Hugo J. Woerdeman

Introduction to Real Analysis, 3rd Edition

Manfred Stoll

Discovering Dynamical Systems Through Experiment and Inquiry

Thomas LoFaro, Jeff Ford

Functional Linear Algebra

Hannah Robbins

Introduction to Financial Mathematics

With Computer Applications

Donald R. Chambers, Qin Lu

Linear Algebra

An Inquiry-based Approach

Jeff Suzuki

Mathematical Modeling in the Age of the Pandemic

William P. Fox

Games, Gambling, and Probability

An Introduction to Mathematics

David G. Taylor

Financial Mathematics

A Comprehensive Treatment in Discrete Time

David G. Taylor

Graph Theory

An Introduction to Proofs, Algorithms, and Applications

Karin R. Saoub

https://www.routledge.com/Textbooks-in-Mathematics/book-series/CANDHTEXBOOMTH

First edition published 2021

by CRC Press

6000 Broken Sound Parkway NW, Suite 300, Boca Raton, FL 33487-2742

and by CRC Press

2 Park Square, Milton Park, Abingdon, Oxon, OX14 4RN

CRC Press is an imprint of Taylor & Francis Group, LLC

The right of Karin R. Saoub to be identified as author of this work has been asserted by her in accordance with sections 77 and 78 of the Copyright, Designs and Patents Act 1988.

Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint.

Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers.

For permission to photocopy or use material electronically from this work, access

Trademark notice: Product or corporate names may be trademarks or registered trademarks and are used only for identification and explanation without intent to infringe.

Library of Congress CataloginginPublication Data

Names: Saoub, Karin R., author.

Title: Graph theory: an introduction to proofs, algorithms, and applications/Karin R. Saoub.

Description: Boca Raton: CRC Press, 2021. | Series: Textbooks in mathematics | Includes bibliographical references and index. | Summary: Graph theory is the study of interactions, conflicts, and connections.

The relationship between collections of discrete objects can inform us about the overall network in which they reside, and graph theory can provide an avenue for analysis. This text, for the first undergraduate course, will explore major topics in graph theory from both a theoretical and applied viewpoint. Topics will progress from understanding basic terminology, to addressing computational questions, and finally ending with broad theoretical results. Examples and exercises will guide the reader through this progression, with particular care in strengthening proof techniques and written mathematical explanations. Current applications and exploratory exercises are provided to further the reader's mathematical reasoning and understanding of the relevance of graph theory to the modern world Provided by publisher.

Identifiers: LCCN 2020053884 (print) | LCCN 2020053885 (ebook) | ISBN 9781138361409 (hardback) | ISBN 9780367743758 (paperback) | ISBN 9781138361416 (ebook)

Subjects: LCSH: Graph theory.

Classification: LCC QA166. S227 2021 (print) | LCC QA166 (ebook) | DDC 511/.5dc23

LC record available at https://lccn.loc.gov/2020053884

LC ebook record available at https://lccn.loc.gov/2020053885

ISBN: 978-1-138-36140-9 (hbk)

ISBN: 978-0-367-74375-8 (pbk)

ISBN: 978-1-138-36141-6 (ebk)

Typeset in Computer Modern font

by KnowledgeWorks Global Ltd

For my children
who inspire me to never stop learning
and for my students
who inspire me to continue writing

At its heart, graph theory is the mathematical study of interactions, conflicts, and connections. The relationship between collections of discrete objects can inform us about the overall network in which they reside, and graph theory can provide one avenue for analysis. In our ever more connected world, understanding the information a connection, or the lack thereof, can provide is extremely powerful.

This text will explore major topics in graph theory from both theoretical and applied viewpoints. Topics will progress from understanding basic terminology, to addressing computational questions, and finally end with broad theoretical results. Examples and exercises will guide the reader through this progression, with particular care in strengthening proof techniques and written mathematical explanations. Current applications and exploratory exercises will be provided where appropriate to further the readers mathematical reasoning and understanding of the relevance of graph theory to the modern world.

The first chapter introduces basic graph theory terminology and mathematical modeling using graphs. Tournaments are used to solidify understanding of terminology and provide an application accessible to the average undergraduate student, followed by some standard graph theory methodology. Graph isomorphism is discussed to provide a theoretical counterpoint and practice in graph drawing. The chapter includes a review of proof techniques featured throughout the book.

The second chapter introduces three major route problems: eulerian circuits, hamiltonian cycles, and shortest paths. Each topic is introduced through its historical origin, followed by a discussion of more modern applications and theoretical implications. These topics allow the reader to delve into processes on a graph, and provide a few areas for practice with graph theory proofs.

The third chapter focuses entirely on treesterminology, applications, and theory. Algorithms for finding a minimum spanning tree are discussed, as well as counting the number of different spanning trees. Trees provide ample areas for improving skills in induction, contradiction proofs, and counting techniques.

The fourth chapter begins with the more theoretical topic of connectivity, a discussion of Mengers Theorem, and ends with flow and capacity and additional applications. Some modern applications are also discussed including centrality measures and their use for network analysis.

The subsequent three chapters each focus around a major graph concept: matching, coloring, and planarity. The standard theoretical aspect of these topics are included, but each chapter brings in a modern application or approach. These include the Stable Marriage Problem, on-line coloring and list coloring, and edge-crossing and thickness.