Graph Theory is the study of objects and the relationships between them. These objects and their relationships are studied using graphs. A graph in Graph Theory is a collection of vertices (which represent the objects) and edges (which represent the relationships between the objects).

The vertices in a graph can represent anything we want them to represent, they don't even have to represent anything if we just want to study the graph. Graphs can be used to study one way or two way relationships. For example if the vertices in a graph represent people and the edges marriage we are showing a two way relationship. If Joe is married to Sally, then Sally has to be married to Joe. Marriage is a two way relationship, we call two way relationships symmetric. If the vertices in our graph represent sports teams and the edges represent beating a team, then our graph is showing one way relationships. If The New York Yankees beat the Boston Red Sox, then the Boston Red Sox can not beat the New York Yankees. When edges represent a one way relationship we call them arcs and put an arrow on them to show which way the relationship is going. We also call graphs that show only one way relationships Directed Graphs, or Digraphs for short.

A graph is called a complete graph when each vertex is related, or adjacent, to every other vertex.

There are many ways a graph can be represented, so far we have been looking at visual representations of graphs. Another way a graph can be represented is by an adjacency matrix . In an adjacency matrix the rows and columns represent the vertices and the entries represent the edges. Here is an example:

This applet will let you see the adjacency matrices of many graphs.

For more information on introductory graph theory watch the following videos: