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.
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.