Section 13-3

Graphs and Networks

The word "graph" in discrete mathematics has a different meaning than usual. It is a collection of dots (vertices) and lines (edges) connecting pairs of dots. People who study graphs and networks are only concerned with the connections, not with the way the graph is drawn. So, in graph theory, the following three pictures all represent the same graph:

In each picture, the neighbors of vertex 1 are 2 and 4; the neighbors of vertex 2 are 1 and 3; the neighbors of vertex 3 are 2 and 4; and the neighbors of vertex 4 are 3 and 1. So these graphs are all isomorphic.

The degree of a vertex is the number of edges connecting it. In the pictures above, all the vertices have degree 2. In the example below, vertex a has degree 5, and the rest have degree 1. A vertex with degree 1 is called an "endvertex" (you can see why).

If a graph has no endvertices, you can ask the question: is it possible to trace over all the edges in the graph exactly once, without lifting your pencil? For instance, is the graph shown below traceable?

The Swiss mathematician Leonhard Euler (a big name in the history of mathematics) solved this problem by reasoning as follows.

Every time you take your pencil through a vertex, you use two edges: one on the way in, and another on the way out. Vertices with odd degrees are going to cause problems: the only way to deal with these are to start tracing or end tracing there. So, a graph is not traceable if it has more than two vertices of odd degree.

By this theorem, the graph above is not traceable, since all four vertices have odd degree (5, 3, 3, and 3).

Euler actually proved the converse of the theorem as well: every graph with no endvertices and with two or fewer vertices of odd degree is traceable.