# Graph Isomorphism

Not what you're looking for?

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.

##### Purchase this Solution

##### 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.

##### 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, ...

###### Education

- AB, Hood College
- PhD, The Catholic University of America
- PhD, The University of Maryland at College Park

###### Recent Feedback

- "Thanks for your assistance. "
- "Thank you. I understand now."
- "Super - Thank You"
- "Very clear. I appreciate your help. Thank you."
- "Great. thank you so much!"

##### Purchase this Solution

##### Free BrainMass Quizzes

##### Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

##### Probability Quiz

Some questions on probability

##### Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

##### Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

##### Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.