Graphs in theory

Graph theory has a humble beginning, as a solution to a puzzle. Residents of the Prussian city of Kongisberg, which was bisected by a river, had long pondered this puzzle. It took Leonard Euler, a mathematician, to not only solve the problem but to do so in such a novel way that his solution launched a new field of mathematics. This chapter reviews the early history of graph theory, starting with the famous story of the seven bridges of Konigsberg. It will also present other early and historically significant uses of graph theory such as Stanley Milgram’s landmark “small world problem” study. Some fundamental topics are introduced such as vertexes and edges. We close out the chapter with an exploration of the four color problem, which was explored and solved using a special type of graph called a planar graph. The four color theorem inspired a mathematician who today lends his name to a graph-inspired distance metric tracked by mathematicians, the Erdos number.

Keywords

Seven Bridges of Konigsberg; Leonard Euler; Eulerian path; Stanley Milgram; six degrees of separation; planar graph; four color theorem; Erdos number

Bridging the history

In 1736, partway through Konigsberg, Prussa, the Pregel River split the city into two parallel segments, inscribing an island between the north and south regions of the city. This island itself was also divided by a stream that connected the two forks of the Pregel River. What we know today is that churning somewhere in the river that simultaneously nourished and partitioned Konigsberg, somewhere streaming amid its divisive canals, Graph Theory was about to surface, and it would change everything.

That city, and the inherent problems bestowed by its water-carved enclaves, was the inspiration for a mathematical puzzle, the Seven Bridges of Konigsberg Problem. There were indeed seven bridges in the city, at least at that time. The Pregel River divided the city into north and south. Bridges connected the resulting islands. The western most island had two bridges to the north and two to the south, the eastern island had one bridge each to the north and to the south, and the two islands themselves were connected by a seventh bridge (Figure 1.1).

Mathematicians wondered, could one walk through the city such that he crosses every bridge once and only once?

Leonard Euler solved this puzzle, and in doing so, laid the foundations for graph theory. In considering the problem, he first stripped away the buildings, the roads, the trees—everything but the bridge crossings themselves, the connections between islands. He saw that the answer, whatever it was, could be represented simply by a sequence of these crossings. That is, the answer might be 3, 6, 4, 5, 7, 1, 2. Or 6, 3, 1, 7, 2, 4, 5. It all depended on how one numbered the bridges. But all that mattered was the order in which the bridges were crossed, not the particular route a person took to reach them. In essence, he reduced the problem to a graph.

Graph theory had not been invented at this point. But in his parlance, Euler saw the land masses as vertexes (also called nodes) and the bridges as edges. These are the building blocks of the simplest graphs—a set of nodes connected to each other by edges.

This simplified formulation of the problem made certain features stand out. For instance, Euler understand that for every land mass, one must enter it via a bridge and then leave it via a different bridge. The exception(s) are the starting and ending land masses. But there are at most two of these (one if the walker starts and ends at the same place); the other land masses are intermediate nodes, which must be entered and exited an equal number of times. Each entrance and exit relies on a unique bridge, so the number of bridges connected to one of these intermediate land masses must be even, or else the walk is doomed from the start (Figure 1.2).

Euler discovered that for a graph like this to have a solution, either all the nodes must have an even number of edges or exactly two of them could have an odd number of edges (in which case the successful walker must start at one of these nodes and end at the other). But all the land regions of Konigsberg had an odd number of bridges. Thus, there was no solution. One could not walk a Eulerian path through Konigsberg (as the goal later became called), and certainly not a Eulerian circuit, which is a walk that starts and ends in the same place.

Often in math or science, whimsical problems that are investigated purely to satisfy the curiosity of those doing the investigating can beget solutions that lead to many important findings. This is true even when the solution is that there is no solution at all. (Though with the bombing of two of the bridges of Konigsberg, now called Kaliningrad, during WWII, a Eulerian path is now possible.) In reducing the problem, transforming bridges to edges and land regions to nodes, Euler generalized it. And his findings, and all those that came after, can apply to any problem which involves entities connected to other entities. Connections are everywhere—from the path of infectious diseases through a population to the circulation of money in an economy. These sets of connections, or networks, can be visualized as graphs, and they can be analyzed with graph theory.

Topology

Before we introduce more examples in the history of graph theory, we should note that Euler’s solution to the Seven Bridges of Konigsberg problem is also seen as a founding work in the field of topology. A graph can be a generalization of a real world network, like the bridges spanning a city. But while that city has a definite north and south and has varying distances between its land regions, once it is translated into a graph, those distinctions no longer matter. A graph can be twisted around. Its nodes can be big or small or different sizes. Its edges can be long or short or even squiggly. This is a central tenet of topology, in which shapes can be transformed into one another as long as certain key features are maintained. For instance, no matter how you bend a convex polyhedron—like a cube or a pyramid—it is always true that V–E+F=2. This is the Euler characteristic, in which F represents the number of faces of the shape, and V and E represent the vertexes and edges we are already familiar with.

The world is teeming with graphs. When you have this mindset, you see them everywhere. Graphs exist in a city’s bridges, in something as small as a pair of dice to something as large as the great Pyramids, and even something as vast and complicated as the internet. (And Google’s search engine, which helps tame that complexity, does so in part by exploiting graph theoretics, as we will see in a later chapter.) This book, as part of a bibliographic network, can exist in a graph. You yourself live in a graph. After all, people (nodes) form relationships (edges) with other people (more nodes), so that the whole of human society comprises one large graph of social connections. One might ask, then, what type of graph are we?

Degrees of separation

Yes, there are different types or classes of graphs. Some graphs have many connections, while some have few. Sometimes these connections cluster around certain key nodes, while other times they are spread evenly across all the nodes. One way to characterize a graph is to find the mean path length between its nodes. How many “degrees of separation” exist between any two nodes? In the 1929 story collection Everything is Different, Hungarian author Frigyes Karinthy posited the notion that everyone is connected by at most five individuals (hence the term, six degrees of separation). One of his characters posed a game—they should select a random individual, then see how many connections it took to reach him, via their personal networks. Stanley Milgram brought this game to life in his “small world experiments” starting in 1967. (These studies are not to be confused with the Milgram Experiment, which tested a person’s willingness to obey authority, even when instructed to deliver seemingly painful shocks to another person, although this too could be graphed.)

Milgram recruited people living in the midwestern United States as starting nodes and had them connect to individuals living in Boston. Note that in a graph, distance has special connotation. The metric distance between two nodes as they are drawn on a sheet of paper is arbitrary. Nodes can be rearranged, shifted closer or farther apart, as long as the connections stay the same. Distance, or path length, refers to the minimum number of edges that must be traveled to go from one node to another within a graph. In Milgram’s small world experiment, it is possible, perhaps even likely, that this path length distance is related to the geographical distance separating two nodes—i.e., Boston to Milwaukee. But in a graph of human social connections, the social circles of two nodes may contribute just as much to the path length distance between them. In choosing his start and end points, Milgram hoped to accommodate both geographic and social distance.

Suppose you were selected as one of his starting points. You would receive a packet in the mail. Inside you would...