Six Degrees of Separation

The word graph has two different meanings in mathematics. One involves plotting the domain and range of a function, and another is used to model relationships between discrete objects.

In this definition, a graph is any set of vertices (dots) in which some pairs of vertices are connected by edges (lines). Often the lines are used to represent relationships between objects (represented by dots).

For example, we can construct a graph in which the vertices represent the people in this class, and we'll draw edges between any two people who mutually know one other. We can measure the "distance" between two vertices A and B by the least number of edges that one has to cross to get from A to B in the graph.

Here's a popular question: what is the minimum distance between any two people in the world, using the graph above?

It is popularly believed that the number is 6 or less for any pair of people. You may have heard the term "six degrees of separation". In fact, in the U.S. it is probably easy to get to anyone using a chain of 3 or fewer people... try using your mayor, congressman, or college professors as intermediate points!

Presentation Suggestions:
If your students like this concept, you can also mention that there is a similar concept of "Erdos number", which is the length of the chain in the graph where edges represent the relations "co-authored a paper with" and distance is measured from a famous (prolific!) number theorist named Paul Erdos. The website in the reference contains a wealth of interesting information about this relation.

The Math Behind the Fact:
Graph theory is an branch of mathematics that is very useful in computer science. You can get an introduction to graph theory in a course on discrete mathematics.

How to Cite this Page:
Su, Francis E., et al. "Six Degrees of Separation." Math Fun Facts. <http://www.math.hmc.edu/funfacts>.

References: The Erdos Number Project web site Keywords:    graph theory Subjects:    combinatorics Level:    Easy Fun Fact suggested by:   Francis Su Suggestions? Use this form. 3.53 current rating Click to rate this Fun Fact...     *   Awesome! I totally dig it!     *   Fun enough to tell a friend!     *   Mildly interesting     *   Not really noteworthy and see the most popular Facts! Get the Math Fun Facts iPhone App!

Want another Math Fun Fact?

For more fun, tour the Mathematics Department at Harvey Mudd College!