138 Chapter 12

Theorem 102. There is no tour of the five-room house that traverses each doorway exactly

once.

Proof. Consider the graph F that abstractly represents the connectivity of the five-room

house. So F has six vertices, one for each room of the house and one vertex for the

exterior region, which we can refer to as the “exterior room.” The graph F has an edge for

each doorway, connecting the vertices associated with each of the rooms that the doorway

connects. A tour of the five-room house traversing each doorway exactly once amounts

to a Euler path in the associated graph F. By inspection, the upper two rooms each have

degree 5 in this graph; the lower three rooms have degree 4, 5, and 4, respectively; and

the exterior room has degree 9. Since we have four vertices with odd degree, the graph F

admits of no Euler path. And so there is no tour of the five-room house that traverses each

doorway exactly once.

We can summarize the argument like this: every time you enter a room by one doorway,

you must exit it by another, and so except for the starting and ending rooms, they must

each have an even number of doors altogether. But they do not, since there are more than

two rooms with an odd number of doors. So it is impossible.

A simple graph is a graph having no edges from a vertex to itself and also no multi-

ple edges between two of its vertices. Thus, a simple graph is essentially a set with an

irreflexive symmetric relation, the edge relation on the vertices.

Theorem 103. In every finite simple graph with at least two vertices, there are two vertices

with the same degree.

Proof. Suppose that G is a simple graph with n vertices, where n ≥ 2. Since no vertex has

an edge with itself, the degree of any vertex in G is an integer from 0 to n − 1, and there

are precisely n numbers in that range. But notice that if there is a vertex with degree n −1,

then it is connected to all the other vertices, and so in this case there cannot be a vertex

of degree 0. (We used our assumption that n ≥ 2 in order to know that 0 and n − 1 are

different numbers.) In other words, the degrees 0 and n −1 cannot both arise as the degree

of a vertex in G. So there are really only n − 1 many possibilities for the degree, and so by

the pigeon-hole principle, there must be at least two vertices with the same degree.

12.4 The Euler characteristic

Let us consider next the Euler characteristic. A finite graph is planar if it can be repre-

sented by vertices and edges in the Cartesian plane without any crossing edges. Such a

graph divides the plane into a finite number of faces, the regions bounded by the edges,

and we count the region totally outside the graph as one of the faces. The Euler character-

istic of any such graph is the quantity v − e + f , where v is the number of vertices, e is the

number of edges, and f is the number of faces.