Graph Theory 101

What is a graph?

A graph G consists of a set V of vertices, and a set E of edges that represent pairwise relations between vertices in V. We say two vertices are adjacent if they share an edge between them.

Here is a graph. Here, V = {1, 2, 3, 4, 5, 6} and E = {{1, 2}, {2, 3}, {2, 4}, {2, 5}, {4, 5}, {5, 6}}. It has 6 vertices, so we say it has order 6. Similarly, it has 6 edges, so we say it has size 6.

Graphs can be used to model all sorts of things, from social networks, to street layouts, to maps. On the next page, I'll introduce a famous problem in graph theory called the graceful labeling problem, which is an interesting puzzle of sorts involving a graph.