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 "coauthored 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>.
