ABSTRACT
This chapter provides an introduction to graph theory. A graph is an abstract structure consisting of vertices and edges, each edge being a pair of vertices; graphs are used to model objects (or people) and the relationships between them. Graph theory is then employed to solve nine puzzles and prove a theorem. The puzzles ask the reader to design an efficient system for linking cities by air, catch a fly on the edges of a cube, compute numbers of handshakes at a party, play a snake game on a chessboard, brace a grid, hire programmers, link wires under a river and deliver mail inefficiently. The theorem shows that the winner of the snake game, with best play, is determined entirely by whether the graph on which the game is played has a “perfect matching”---that is, a collection of disjoint edges that together include every vertex in the graph.
