Example: Graphs, Maps and Isomorphism (Sheet M)

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

Often, some people find it is difficult to capture the full meaning of ideas from formal definitions. In this context it is helpful to have concrete examples which make the issues implicit in the definitions more transparent.

The concepts of a graph, and a plane graph (one drawn in the plane so that edges meet only at vertices) provide an instance of this kind of issue. When graph G has been drawn in the plane it gives rise to a "face structure." These faces of a plane graph are sometimes known as the map associated with the graph. I use pi to denote the number of faces with i sides in a plane graph.

We have seen many examples where two graphs are not isomorphic despite the fact that they have the same valences (degrees). We have also seen that isomorphic planar graphs G and H can have different maps associated with them when drawn in the plane. We can tell the maps are different because the they have different numbers of faces with i sides.

Can it happen that two maps in the plane, arising from non-isomorphic graphs G and H can, can have the same numbers of faces with i sides? Think about the two maps below which correspond to plane graph drawings of the graphs G and H?

Graph G drawn in the plane: Graph H drawn in the plane: 1. Write down the non-zero values of pi for the different i which are possible for G.

2. Write down the non-zero values of pi for the different i which are possible for H.

3. Are the values you get in 1. and 2. the same or different?

4. Are the graphs G and H isomorphic? If they are not isomorphic, how did you determine this? Were you able to tell G and H apart using their valences (degrees)?

Note that Hassler Whitney showed that when planar graphs (no loops or multiple edges) are 3-connected the map structures of the plane drawings of a fixed graph G (that is, it is planar and 3-connected) are the same. Thus, the infinite face of such a graph may have a different number of sides from one that another drawing of the same graph has, but the maps involved are essentially the same.