- Grasping Graph Theory
- Old and Famous Problems
- Graphs, Computers, and Popular Culture
- Constructing a Simple Graph with Boost
- Adding Values to Vertices and Edges
- Manipulating Property Values
- Adding Vertices and Edges
- Iterating Through the Edges and Vertices
- Solving Problems with Graphs and Boost
- Conclusion

## Old and Famous Problems

Graphs aren’t just for representing data. They’re often used in problem solving, and, as such, play a central role in many algorithms. Over the years, mathematicians have used graphs to solve many famous problems. One of the most famous is calculating how many colors are needed to color each country on a world map, such that no two adjacent countries share the same color. (If two countries touch at a single point, that point isn’t considered a boundary.) People have long suspected that the answer is four, and thus the problem can be to prove that any map can be colored with only four colors.

This assertion has been proven in various ways. One way employs graph
theory—in particular, planar graphs. Remember that a planar graph is
simply a graph that can be drawn on paper (that is, in two dimensions) without
any edges crossing. The vertices in the graph represent countries, and the edges
represent adjacencies. Thus, if a line connects two countries in a graph, the
two countries share a common border. By this representation, the assertion
becomes the following: *Given any planar graph, a number can be associated
with each vertex, and only four numbers are needed such that no two adjacent
vertices share a single number.* That hypothesis can then be proven using
graph theory. (I won’t go into the details here, but you can find
information on the web if you’re curious. It’s called the "Four
Color Theorem.")

Another famous problem that can be proven using graph theory is the "Seven Bridges" problem. The problem is based on the bridges of Konigsberg, Prussia. The problem is whether it’s possible to walk across each bridge in that city once and only once (without cheating by swimming across a river), and ultimately return to the starting point. The famous mathematician Leonhard Euler solved the problem by using graph theory. (Unfortunately, his proof shows that it’s impossible to perform the feat without jumping into one of the rivers.)

In Euler’s proof of the Seven Bridges problem, he let the vertices of a
graph represent the land masses, and the edges of the graph represented the
bridges. To solve the problem, Euler associated a *degree* with each
vertex; the degree is the number of edges touching the vertex. Euler proved that
in order to complete a single circuit (that is, to cross each bridge once and
only once and to return to your starting point), all the nodes must have a
degree that’s positive. If any nodes have an odd number of edges touching
them, then the task is impossible. The seven bridges in Konigsberg were
constructed such that four of the nodes have odd degrees.