Difficult problem for isomorphism in graph

• Nov 3rd 2009, 09:49 AM
ilovebillu
Difficult problem for isomorphism in graph
Let G10 be a simple graph of 10 vertices, and G10' its complement. As we know, the relationship between 10G and 10G is as follows: (1) they have the identical set of vertices; (2) two distinct vertices are adjacent in G10' if, and only if, they are not adjacent in 10G. Prove that 10G cannot be isomorphic to G10'.

• Nov 3rd 2009, 10:00 AM
Plato
Quote:

Originally Posted by ilovebillu
Let 10G be a simple graph of 10 vertices, and 10G its complement. As we know, the relationship between 10G and 10G is as follows: (1) they have the identical set of vertices; (2) two distinct vertices are adjacent in 10G if, and only if, they are not adjacent in 10G. Prove that 10G cannot be isomorphic to 10G.

Please reread this post. You have used 10G to name two different graphs have you not?
Did you perhaps mean 10C for the complement?
Please edit the post to make corrections.
Or explain what is meant.
• Nov 3rd 2009, 10:16 AM
ilovebillu
Ooops... sorry..yeah did the corrections
• Nov 3rd 2009, 11:14 AM
Plato
Here is a big hint.
The union of a graph and its complement is a complete graph.
A complete graph of order ten has forty-five edges.