*Arthur Benjamin, Gary Chartrand, and Ping Zhang*

- Published in print:
- 2017
- Published Online:
- May 2018
- ISBN:
- 9780691175638
- eISBN:
- 9781400852000
- Item type:
- chapter

- Publisher:
- Princeton University Press
- DOI:
- 10.23943/princeton/9780691175638.003.0001
- Subject:
- Mathematics, Applied Mathematics

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

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

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.