*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.0005
- Subject:
- Mathematics, Applied Mathematics

This chapter considers Eulerian graphs, a class of graphs named for the Swiss mathematician Leonhard Euler. It begins with a discussion of the the Königsberg Bridge Problem and its connection to ...
More

This chapter considers Eulerian graphs, a class of graphs named for the Swiss mathematician Leonhard Euler. It begins with a discussion of the the Königsberg Bridge Problem and its connection to Euler, who presented the first solution of the problem in a 1735 paper. Euler showed that it was impossible to stroll through the city of Königsberg, the capital of German East Prussia, and cross each bridge exactly once. He also mentioned in his paper a problem whose solution uses the geometry of position to which Gottfried Leibniz had referred. The chapter concludes with another problem, the Chinese Postman Problem, which deals with minimizing the length of a round-trip that a letter carrier might take.Less

This chapter considers Eulerian graphs, a class of graphs named for the Swiss mathematician Leonhard Euler. It begins with a discussion of the the Königsberg Bridge Problem and its connection to Euler, who presented the first solution of the problem in a 1735 paper. Euler showed that it was impossible to stroll through the city of Königsberg, the capital of German East Prussia, and cross each bridge exactly once. He also mentioned in his paper a problem whose solution uses the geometry of position to which Gottfried Leibniz had referred. The chapter concludes with another problem, the Chinese Postman Problem, which deals with minimizing the length of a round-trip that a letter carrier might take.

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

*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.0013
- Subject:
- Mathematics, Applied Mathematics

This book concludes with an epilogue, which traces the evolution of graph theory, from the conceptualization of the Königsberg Bridge Problem and its generalization by Leonhard Euler, whose solution ...
More

This book concludes with an epilogue, which traces the evolution of graph theory, from the conceptualization of the Königsberg Bridge Problem and its generalization by Leonhard Euler, whose solution led to the subject of Eulerian graphs, to the various efforts to solve the Four Color Problem. It considers elements of graph theory found in games and puzzles of the past, and the famous mathematicians involved including Sir William Rowan Hamilton and William Tutte. It also discusses the remarkable increase since the 1960s in the number of mathematicians worldwide devoted to graph theory, along with research journals, books, and monographs that have graph theory as a subject. Finally, it looks at the growth in applications of graph theory dealing with communication and social networks and the Internet in the digital age and the age of technology.Less

This book concludes with an epilogue, which traces the evolution of graph theory, from the conceptualization of the Königsberg Bridge Problem and its generalization by Leonhard Euler, whose solution led to the subject of Eulerian graphs, to the various efforts to solve the Four Color Problem. It considers elements of graph theory found in games and puzzles of the past, and the famous mathematicians involved including Sir William Rowan Hamilton and William Tutte. It also discusses the remarkable increase since the 1960s in the number of mathematicians worldwide devoted to graph theory, along with research journals, books, and monographs that have graph theory as a subject. Finally, it looks at the growth in applications of graph theory dealing with communication and social networks and the Internet in the digital age and the age of technology.