"Graph Theory in Practice: Part I," by Brian Hayes. American Scientist, January/February 2000, pages 9-13.
A mathematical graph is in one sense a simple creature: It consists of a set of vertices (or nodes) connected by edges (or links). And yet graphs can exhibit high complicated behavior, and an entire mathematical theory has been developed to understand them. This article discusses the branch of mathematics known as graph theory and how this theory is used to analyze the characteristics of graphs. One of the examples discussed in the article is the well-known phenomenon of "six degrees of separation"---the idea that any two people in the world are, on average, connected by six acquaintances. In this case, people are the vertices of the graph, and acquaintanceships form the edges. A similar question arises with the World Wide Web: How many "clicks" is away is a given web page from any other?
--- Allyn Jackson