Ian Short - Introduction to graph theory

Introduction to graph theory

22 March 2010

Introduction

A graph consists of a collection of points and a collection of lines joining certain pairs of the points. Three examples of graphs are displayed below. The points, shown as blue spots, are called vertices, and the lines, shown in black, are called edges. It does not matter what the vertices or edges look like, or how they are positioned. (The edges may even be curved lines, and they may intersect). Two of the graphs below are, in fact, the same. Using the drag tool, try to work out which of the two graphs are the same.

Graphs can have an infinite number of vertices. For example, imagine a graph with vertices labelled 1,2,3,..., and with an edge connecting vertex n to vertex n+1 for each positive integer value of n. In these notes we are only interested in graphs with a finite number of vertices and edges. Each pair of vertices may only have one edge connecting the two vertices. And a vertex is not allowed an edge to itself. (Objects with the restrictions stated in the last two sentences are somtimes called simple graphs.)

We finish this section with a question. Two of the graphs shown above are the same. Can you be sure that all three of the graphs are not the same?

Investigation 1: complete graphs

This section is concerned with the question, what is the maximum number of edges a graph with n vertices may have? Consider this question before you read on.

Five different graphs are displayed below. What do you notice about them?

The first graph has one vertex, the second graph has two vertices, the third graph has three vertices, and so forth. Each graph is such that every pair of vertices in that graph is joined by an edge. These are graphs for which no more edges can be added. They are called complete graphs. Specifically, a complete graph is a graph such that each pair of vertices is joined by an edge. The complete graph with n vertices is denoted K_n. Thus the question at the beginning of this section is equivalent to the question, how many vertices does K_n have?

In stark contrast to complete graphs, an empty graph is a graph with no edges.

Investigation 2: graph counting

How many graphs are there with n vertices? This is a more complicated question than that of the last section, so let us satisfy ourselves by examining only low values of n. First, n=1. There is only one graph with one vertex; there are no other vertices to connect up with edges. Next, n=2. There are two possible graphs with two vertices; the complete graph and the empty graph. What about three vertices? The possible graphs with three vertices are displayed below.

The task of this investigation is for you to construct, using Graph Constructor, all the graphs with four vertices. Be careful not to include duplicates.

Investigation 3: degrees

The degree of a vertex is the number of edges that connect to that vertex. In the graph below, each vertex is labelled with its degree.

Add up all the vertex degrees in the graph above. Now count the number of edges in the graph above. How are the two numbers you have calculated related? Do the same for other graphs. What do you notice? Can you prove anything?

Once you feel you have fully understood the purpose of the previous paragraph, answer the following question: is there a graph for which the number of vertices of odd degree is even?

Investigation 4: distinguishing graphs

How can we determine if two graphs are different? We can count the number of vertices on each of the graphs; if we obtain two different numbers then the graphs differ. Likewise we can compare the number of edges. Another idea is to calculate the collection of vertex degrees for each graph, and compare the two collections. Examine the two graphs below.

Are these two graphs the same? Try counting vertices and edges, and calculating vertex degrees. If you cannot distinguish the two graphs with these quantities, then how can you distinguish the two graphs?

Investigation 5: a problem

Here is a problem that can be solved using basic graph theory. We begin with the observation that every pair of people in the world are either friends, or they are not friends. Now take any group of six people. Prove that, within that group, either there is a subgroup of three people who are all mutually friends, or there is a subgroup of three people who are all mutually not friends. Try to answer this question before you read on for a hint.

Here is a hint for the preceding problem. We represent each of the six people by a vertex on a graph. Let us pick any member of the group of six, and colour him green. Consider his relationship to the other five people: since there are five of them, he must either be friends with three of them, or he must be not friends with three of them. Suppose that he is friends with three of them (the other case can be dealt with similarly). Then we draw an edge between two vertices if and only if the two vertices represent friends. In the graph below, three of the friends of the green person are represented by edges. Focus on these three friends of the green person, and the green person himself; what can we deduce about this subgroup of people?