Advanced High-School Mathematics

SECTION 2.2 Elementary Graph Theory 135

such that{f(v 1 ),f(w 1 )}is an edge of G 2 exactly when{v 1 ,w 1 } is an
edge ofG 1. In other words, two graphs are isomorphic exactly when
one is simply a redrawing of the other. A moment’s thought reveals
that the two graphs depicted below are isomorphic.

Assume thatG 1 andG 2 are graphs and that

f : vertices ofG 1 −→ vertices ofG 2

determines an isomorphism between these graphs. Ifv 1 is a vertex of
G 1 , and ifv 2 =f(v 1 ), it should be instantly clear thatv 1 andv 2 have
the same degree. However, this condition isn’t sufficient; see Exercise
1 on page 141.

There are two important families of graphs that warrant special con-
sideration. The first is the family ofcomplete graphsK 1 , K 2 , K 3 , ...
(see also page 118). The graphKnis the simple graph (see page 109)
havingnvertices and such that every vertex is adjacent to every other
vertex.