Determine if G and H are isomorphic. (graphic included)

[hyderman]

Please explain the steps . Thank you!

 

[Pilly151]

These two graphs are NOT isomorphic. Although the vertices have a one-to-one correspondence, there is not and onto function from one to the other since corresponding vertices are incident to different edges.

 

[pka]

Here is a simple way to see that the graphs are not isomorphic.
Look at the complement of each graph.
One is connected and one is not.

 

[hyderman]

Here is a simple way to see that the graphs are not isomorphic.
Look at the complement of each graph.
One is connected and one is not.

thanx pka .... i am not sure about the complement of the graph, could you please explain how the complement will determine that. i really appreciate your help

thanx muchhhhh

 

[stapel]

i am not sure about the complement of the graph, could you please explain how the complement will determine that.

The tutor already explained how the complements would show that the graphs are not isomorphic: "One is connected and one is not."

Are you not familiar with the definition of "isomorphic"?

Thank you.

Eliz.

 

[daon]

I'm no expert, but aren't the complements both disconnected? e is adjacent to all nodes in G and 1 is adjacent to all nodes in H.

 

[hyderman]

no i am not familiar with isomorphic.... i am starting to learn it and i am having problem understanding it, its confusing according to the book in order to know if its isomorphic or not :
first check the vertices degrees .... now in this question i have to check if its one to one or onto..... this matterial goes back to my first year...... now i am in my final year and i have to remember all the stuff such as one to one or onto AND complement of the graph .... so i just need step by step to refresh my memory
thanx much

 

[pka]

If two graphs are isomorphic if and only if the two are essentially the same graph.
There is a bijection between the vertex sets that is edge preserving. That is two vertices are adjacent is one graph if and only if their images are adjacent in the other graph.

Isomorphic graph have the same degree sequence: this is necessary but not sufficient.
If two graphs are isomorphic then their adjacency matrices are similar.
If two graphs are isomorphic then their complements are isomorphic.

It is this last case that I suggest you use to see that the graphs are not isomorphic. Because each of these “close” to complete. Therefore, looking at the complements, and ignoring isolated points, you will see one of the complements will have only one non-trivial component while the other has two.

If you do not know about complements: the complement of a graph G is a graph, G’, on the same of vertices and G’ has an edge if and only if that edge is not in G.