Brief Introduction to Graph Theory

Prepared by:

Joseph Malkevitch
Department of Mathematics and Computer Studies
York College (CUNY)
Jamaica, New York

email:

malkevitch@york.cuny.edu

web page:

http://york.cuny.edu/~malk

Graph theory provides a powerful tool for constructing mathematical models in a variety of situations. Given "objects," one can represent them by dots and the relationship between the objects can be indicated using straight or curved line segments. Dots might represent people, street corners, or books. Line segments could indicate that the people are friends, that street corners are connected by a street, or that the books have the same author.

The power of graph theory lies in its great flexibility for capturing a variety of situations that arise over a broad array of fields - biology, chemistry, mathematics, physics, economics, operations research, psychology, etc.

Graphs can have labels on the vertices or can be unlabeled. Graphs can have weights on the edges or not. The weights can represent costs, times, distances, intensity of feelings, or many other quantities. A generalization of the graph concept is to directed graphs. In a directed graph, or digraph, each edge gets a direction (an arrow) which captures some aspect of the "relationship" that is to be studied. For example, if the vertices represent players in a tennis tournament, a directed edge from Mary to Sally would mean that Mary won her match against Sally. Digraphs can also be used to code the information about the one-way nature of streets in a street network.

Often it is of interest to be able to record the way one moves between vertices in a graph using the edge,. for example, inspecting for potholes in a street network or checking that the traffic signal at each corner of a street network is operating properly. Ideas of this kind will be illustrated using the graph below.

We will be interested in both the situation where one starts and ends one's "tour" of a part (or all) of a graph using edges at the same vertex or at a different vertex from where the tour started.

Open: This indicate the tour starts and ends at different vertices.

Closed: This indicates that the tour starts and ends at the same vertex.

Walk: No edges or vertices of the tour are repeated.

Trail: No edges can be repeated but a vertex may be repeated.

Path: No vertices or edges can be repeated.
When one refers to a path, trail or walk without saying specifically that it is open or closed, then it is usually taken to mean one has an open path, walk, or train in mind.

Examples: (Vertices are listed, and separated by commas)

(Open) walk 5, 6, 9, 0, 9, 2, 9, 7

(Open) trail: 5, 6, 9, 2, 3, 9, 8, 10

(Open) path: 3, 2, 9, 7, 10, 8

Closed walk: 7, 9, 2, 9, 0, 9, 7

Closed trail: 7, 10, 8, 9, 2, 3, 9, 7

Closed path: 2, 3, 9, 2

Another name for a closed path is a circuit (sometimes cycle).

Note that in the circuit, 2, 3, 9, 2 it is not considered that 2 has been revisited because we start and end at the same vertex. In the closed trail, 7, 10, 8, 9, 2, 3, 9, 7 we have revisited vertex 9 but not vertex 7.

Note there are many different ways to represent the same circuit: 2, 3, 9, 2 can also be represented 2, 9, 3, 2 or 3, 9, 2, 3.