Share
Explore BrainMass

Graph Isomorphism

What does it mean for two graphs to be the same? Let G and H be graphs. We say that G is isomorphic to H provided that there is a bijection f:V(G) -> V(H) so that for all a, b, in V(G) there is an edge connecting a and b (in G) if and only if there is an edge connecting f(a) and f(b) (in H). The function f is called an isomorphism of G to H.

We can think of f as renaming the vertices of G with the names of the vertices of H in a way that preserves adjacency. Less formally, isomorphic graphs have the same drawing (except for the names of the vertices).

Do the following:

(a) Prove that isomorphic graphs have the same number of vertices.
(b) Prove that if f:V(G) -> V(H) is an isomorphism of graphs G and H and if v is an element of V(G), then the degree of v in G equals the degree of f(v) in H.
(c) Prove that isomorphic graphs have the same number of edges.
(d) Give an example of two non-isomorphic graphs that have the same number of vertices and the same number of edges.

Attachments

Solution Preview

(a) Proof that isomorphic graphs have the same number of vertices:

If graphs G and H are isomorphic, there is a bijection f:V(G) -> V(H), where V(G) and V(H) are the vertex sets of G and H, respectively.

A bijection is a one-to-one, onto function. Since f is one-to-one, at most one element of V(G) is mapped (via f) to a given element of V(H), so |V(G)| <= |V(H)|, where |V(G)| and |V(H)| denote the cardinalities of V(G) and V(H), respectively (i.e., the number of elements of V(G) and V(H), respectively).

Since f is onto, every element of V(H) is the image of at least one element of V(G) under the mapping f, ...

Solution Summary

Step-by-step proofs of parts (a) through (c) are given. For (d), an example of a pair of non-isomorphic graphs with the same number of vertices and the same number of edges is provided in an attached .doc file.

$2.19