Graph Theory Lessons


previous index next Lesson 1: Graphs, Vertices, and Edges

A graph is a non-empty finite set V of elements called vertices together with a possibly empty set E of pairs of vertices called edges. Here are a few examples of graphs:

  • Vertex set V={a, b, c, d} and edge set E={(a, b), (b, d)}
  • Vertex set V={1, 2, 3, 4} and edge set E={(2, 4)}
  • Vertex set V={wolf, goat, cabbage} and edge set E={(wolf, cabbage)}
  • Vertex set V={A, B, C} and edge set E={}

We can draw pictures to represent graphs. Vertices are represented by dots and an edge (v, w) by an arc that starts from the dot representing v and ends at the dot representing w.

The simplest type of graph is a null graph. It consists of a non-empty finite set of vertices and no edges.

Java Web Start Activity:
To get examples of null graphs, launch the Java Web Start application by clicking on the link below this paragraph. Once the application is running, click on the + button to increase the number of vertices. Click on the - button to decrease the number of vertices.

Petersen activity:
We shall use this activity to introduce you to the program Petersen. You need Java 6 or later to run the program. You can download the jar file for Petersen using the link "Getting Petersen" above. Windows users can start the program by double clicking on the jar file. For other platforms, there are instructions on download page for starting the program from a command console. After the welcome message and copyright notice you will get a screen with a graph drawn on it. This graph is called the Petersen Graph after Julius Petersen.

To get a null graph, click on the Graph menu item and then select Named Graph followed by Null Graph. In future we shall represent such a sequence of clicks as Graph | Named Graph | Null Graph. You will get an input box with the question 'How many vertices? Press 4 and then press the Enter key (or click OK.) You will get four vertices on the screen like in Fig. 1.1 The title 'N(4)' at the top of the frame in the program means Null graph on four vertices, sometimes written as N 4 .

the null graph on four vertices
Fig 1.1. The null graph N 4

In a similar way, try to get the null graph with 10 vertices called N 10. Notice that the labels 1, 2, 3, etc. are the same color as the vertices they refer to. This will be useful when you have many vertices on the screen. You can move the vertices around by dragging them with the mouse. If the colors don't come out well on your monitor you can turn the color off by clicking the menu item Picture, and then unchecking the radio button labeled Color on/off. Try a few other null graphs like N 25 and so on.

There will be a limit on the number of vertices the program can handle. This limit depends on the version of the program and the license installed. It can be anything from 10 to 1000. Other limitations will be the amount of memory available to you and the amount of screen space you have. Some algorithms take a very long time to run when the graphs are large. If you need to examine larger graphs you can get a license from the download page. You install the license by selecting Help | License in the program and pasting the license in the lower part of the dialog. Restart the program and you should be able to load larger graphs.

Null graphs are not very interesting so let us introduce some edges. If an edge e = (v, w), where v and w are vertices we call v and w the end vertices of e. The edge will be represented in the picture by an arc or a line segment from one end vertex to the other. Two vertices v and w are adjacent if there is an edge e = (v, w) in the graph. We also say that the edge e is incident to the vertex v (and also to vertex w). The Petersen graph, for example, has ten vertices and fifteen edges. If an edge has the form e = (v, v), i.e., it starts and ends at the same vertex we shall call it a loop. The Petersen graph has no loops.

The Petersen graph in the Petersen program
Fig 1.2. The Petersen graph

Petersen activity:
In the Petersen program, use the procedure outlined above to get N4 on your screen as in fig. 1.1. On the menu, click Mouse | Add/Delete Edge | Straight.

Menu item to add a straight edge to a graph
Fig 1.3. Menu item to add a straight edge to a graph
To add an edge from vertex 3 to vertex 2 you drag the mouse from vertex 3 to vertex 2. Your graph should now look like fig. 1.4. To erase an edge you do the same thing: drag the mouse from one vertex to the other. If you would like to change the shape of the vertices click Picture | Vertices | Shape and you will get some choices.

a graph with four vertices and one edge
Fig 1.4. A graph with four vertices and one edge

Experiment and add edges to graphs as you wish. In most of the material in this course we shall talk about simple graphs. A simple graph has no more than one edge between vertices and no loops.

Sometimes you will need to store your graph on disk so let us learn how to save and restore a graph. Get the graph N25 as above. To save it, click Graph | Write Graph to Disk. You will get a file chooser dialog to choose the location and name for the graph on your file system. The files are stored with a .pet extension. Now suppose at a later time you want to read this graph from the disk. To restore the graph from your disk drive click Graph | Read Graph from Disk. You will get a file chooser dialog to choose the location and name of the file you want to read into the program.

The program can also create JPEG images. To create a JPEG click Graph | Write JPEG to Disk. You can view the JPEG file in your favorite graphics program.

There are many interesting graphs so let us look at a few of them. Many graphs have names. The Petersen program has some named graphs. You get them by clicking Graph | Named Graph.

Complete graphs are graphs in which every vertex is adjacent to every other vertex. To get a complete graph, click Graph | Named Graph | Complete | Complete Graph. You will be asked how many vertices you want. Input an integer (e.g. 5). You will then get the complete graph on 5 vertices which we will call K5 for short.

A complete bipartite graph has the vertices in two groups (let us call them left and right). All the vertices in one group are adjacent to all the vertices in the other but vertices in the same group are not adjacent to one another. To get a complete bipartite graph click Graph | Named Graph | Complete | Complete Bipartite Graph. You will be asked how many vertices you want on the left and on the right. Try 4 vertices on the left and 3 on the right to get the graph we will call K4,3. Examine some of the other named graphs in the program.

Programming Task

© C. Mawata