Problem Solving and Modeling with Graph Theory
Dennis Geller (Arlington High School)
Graph Theory is almost unique among the mathematical disciplines: the basic concepts are very simple, and most everyone has encountered problems that involve graph theory. It is not a huge step to get from basic definitions to asking interesting questions, some of which are easily settled, and some of which are among the major unsolved problems of mathematics. Graph Theory is a branch of Discrete Mathematics that studies structures expressed as points connected by lines. Graphs are used as models in fields as diverse as psychology, physics, political science, and drama.
This institute will look at graphs as they occur in mathematical problems and at graphs as mathematical models both to represent and to solve problems in a variety of areas. Although no prior background is required, we'll see how the study of graphs makes it possible for all of us to understand how (and why) mathematicians work. We will explore both familiar and unfamiliar puzzles and see how using graphs as models help us find solutions while at the same time allowing us to think deeply and more abstractly. All of
the puzzles will be easily understood by middle and high school students, and can be made the basis of various problem-solving activities. Yet, as we'll see, they extend naturally into problems that challenge even the best mathematicians. They serve as an ideal tool for developing and refining mathematical habits of mind - such as geometrical visualization, algebraic abstraction, and logical induction and deduction - both in our students and in ourselves.
Topics will include familiar problems like those involving paths (The Konigsberg Bridge, the Traveling Salesman Problem) and map colorings, applications to other fields such as social psychology and electrical circuits, applications of other mathematical concepts to graphs, and some notions that are simply fascinating and fun!