Lecture 1

• British Midland International route map (UK & Ireland)
• Delta Airlinesroute map (North America)
• The London Underground route map
• An example of a geometric graph (two vertices are adjacent if the Euclidean distance between them is below a certain threshold; used to model, for example, sensor networks)
• The 48 contiguous U.S. states, with two states adjacent if they share a common boundary
• My Facebook Friendship graph - vertices are my friends, and two vertices are adjacent if those two people are themselves Facebook friends
• A very small portion the Kevin Bacon graph - vertices are actors and movies, and an edge joins an actor and a movie if that actor featured in that movie
• A small portion of the collaboration graph - vertices are mathematicians, edges indicate pairs of mathematicians who have collaborated on a published reasearch paper (this portion drawn in 1979)
• The vast Internet graph - vertices are websites, with edges representing hyperlinks