Jump to ContentJump to Main Navigation
The Fascinating World of Graph Theory$
Users without a subscription are not able to see the full content.

Ping Zhang, Gary Chartrand, and Arthur Benjamin

Print publication date: 2017

Print ISBN-13: 9780691175638

Published to Princeton Scholarship Online: May 2018

DOI: 10.23943/princeton/9780691175638.001.0001

Show Summary Details
Page of

PRINTED FROM PRINCETON SCHOLARSHIP ONLINE (www.princeton.universitypressscholarship.com). (c) Copyright Princeton University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in PRSO for personal use.date: 04 June 2020

Introducing Graphs

Introducing Graphs

(p.1) 1 Introducing Graphs
The Fascinating World of Graph Theory

Arthur Benjamin

Gary Chartrand

Ping Zhang

Princeton University Press

This chapter provides an introduction to graphs, a mathematical structure for visualizing, analyzing, and generalizing a situation or problem. It first consider four problems that have a distinct mathematical flavor: the Problem of the Five Princes, the Three Houses and Three Utilities Problem, the Three Friends or Three Strangers Problem, and the Job-Hunters Problem. This is followed by discussion of four problems that are not only important in the history of graph theory, but which led to new areas within graph theory: the Königsberg Bridge Problem, the Four Color Problem, the Polyhedron Problem, and the Around the World Problem. The chapter also explores puzzles and problems involving chess that have connections to graph theory before concluding with an overview of the First Theorem of Graph Theory, which is concerned with what happens when the degrees of all vertices of a graph are added.

Keywords:   graph, Problem of the Five Princes, Three Friends or Three Strangers Problem, Job-Hunters Problem, graph theory, Königsberg Bridge Problem, Four Color Problem, Polyhedron Problem, Around the World Problem, First Theorem of Graph Theory

Princeton Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us.